const swap = (arr, i, j) => {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
const partition = (arr, left, right) => {
const pivot = arr[Math.floor(Math.random() * (arr.length - left) + left)];
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
return left;
};
const quickSort = (arr, left, right) => {
if (left === undefined) {
left = 0;
right = arr.length - 1;
}
if (left >= right) {
return arr;
}
const pIndex = partition(arr, left, right);
quickSort(arr, left, pIndex - 1);
quickSort(arr, pIndex, right);
return arr;
};
I’m always getting the right results, but I used a tool to check the time it takes to run, and it varies drastically for large inputs. I imagine it has to do with the random pivot, but I’m still not convinced that’s it. I’m kind of new to sorting algorithms and I’ve been analyzing the code in a debugger for awhile, but I’m not sure that there isn’t a mistake or inaccuracy somewhere. I’d appreciate if someone can look it over and verify whether or not this algorithm is implemented correctly. Let’s assume for now that I want to maintain the random pivot over picking the middle element, or some other way.
>Solution :
Yes, your choice of the pivot is broken. You’re choosing an element anywhere from left
to the end of the array, not an element between left
and right
.