Repository navigation
The function patition for quickSort can't support array which has duplicates. #202
Description
It is a good way to patition a deduplicated array , but if the unsorted array is [1,2,3,4,4,4,2,4,4,6,7], the function can't move 2 to front.
I'd like to write a patition function like this:
function partition(array, left, right, compareFn) {
const pivot = array[Math.floor((right + left) / 2)];
let l = left;
let r = right;
let i = left;
while (i <= r) {
if (compareFn(array[i], pivot) === Compare.LESS_THAN) {
swap(array, i, l);
i++;
l++;
}
else if (compareFn(array[i], pivot) === Compare.BIGGER_THAN) {
swap(arr, i, r);
r--;
}
else {
i++;
}
}
// return [l, r];
return l;
}PS：I learned a lot from your book, thank you~
Activity