I’m currently learning some sorting algorithms and I made my realisation of quick sort, but it didn’t work properly. Instead of just sorting the array, it deleted duplicate values. Here is my code:
function quickSort(array) {
if (array.length <= 1) return array;
let pivotIndex = Math.floor(array.length / 2);
let pivot = array[pivotIndex];
let less = [];
let greater = [];
for (let i = 0; i < array.length; i++) {
count++;
if (i === pivotIndex) continue;
if (array[i] < pivot) { // *
less.push(array[i]);
}
if (array[i] > pivot) {
greater.push(array[i])
}
}
return [...quickSort(less), pivot, ...quickSort(greater)];
}
When I replaced two if’s (starting from line *) to the following code, it started working:
if (array[i] < pivot) {
less.push(array[i]);
} else {
greater.push(array[i])
}
I just don’t understand what the difference and why the first variant isn’t working?
And also why it works longer than selection sort or sometimes even bubble sort?
I also tried adding "continue" in the end of each if, but it doesn’t help.
3
Answers
Replace:
With:
In this option you miss values
array[i] === pivot
. Thus deleting them.Note that if
array[i] > pivot
, code (1) will do nothing but (2) will pusharray[i]
togreater
. So it will behave differently when there are duplicate values inarray
.