You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
In the partition function:
fn partition(list: &mut [i32], left: usize, right: usize, pivot_index: usize) -> usize {
let pivot_value = list[pivot_index];
list.swap(pivot_index, right); // Move pivot to end
let mut store_index = left;
for i in left..(right + 1) {
if list[i] < pivot_value {
list.swap(store_index, i);
store_index += 1;
}
list.swap(right, store_index); // Move pivot to its final place
}
store_index
}
in the range of (left..right+1),the list.swap(right,store_index) should be placed out of the iteration.
here the pesudo code in wiki:
function partition(list, left, right, pivotIndex) is
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right − 1 do
if list[i] < pivotValue then
swap list[storeIndex] and list[i]
increment storeIndex
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
The text was updated successfully, but these errors were encountered:
fn it_works() {
let mut arr1 = [2, 3, 4, 5];
assert_eq!(quick_select(&mut arr1, 0, 3, 1), 3);
let mut arr2 = [2, 5, 9, 12, 16];
assert_eq!(quick_select(&mut arr2, 1, 3, 2), 12);
let mut arr2 = [0, 3, 8];
assert_eq!(quick_select(&mut arr2, 0, 0, 0), 0);
}
in the second instance of the test, the right answer should be 9, not 12.
In the partition function:
fn partition(list: &mut [i32], left: usize, right: usize, pivot_index: usize) -> usize {
let pivot_value = list[pivot_index];
list.swap(pivot_index, right); // Move pivot to end
let mut store_index = left;
for i in left..(right + 1) {
if list[i] < pivot_value {
list.swap(store_index, i);
store_index += 1;
}
list.swap(right, store_index); // Move pivot to its final place
}
store_index
}
in the range of (left..right+1),the list.swap(right,store_index) should be placed out of the iteration.
here the pesudo code in wiki:
function partition(list, left, right, pivotIndex) is
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right − 1 do
if list[i] < pivotValue then
swap list[storeIndex] and list[i]
increment storeIndex
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
The text was updated successfully, but these errors were encountered: