Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

A small bug in Quick Select algorithm #714

Open
lvyuemeng opened this issue May 12, 2024 · 1 comment
Open

A small bug in Quick Select algorithm #714

lvyuemeng opened this issue May 12, 2024 · 1 comment

Comments

@lvyuemeng
Copy link

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

@lvyuemeng
Copy link
Author

lvyuemeng commented May 12, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant