My experience with QuickSort involved testing two algorithms on LeetCode for a specific problem. Surprisingly, both algorithms worked, but one outperformed the other significantly, leaving me puzzled about the reason behind the speed difference.
One of the algorithms exceeded the time limit set by LeetCode:
function quickSort(array) {
quickSortHelper(array, 0, array.length - 1);
return array;
}
function quickSortHelper(array, start, end) {
// Handling edge case
if(start >= end) return;
// Always selecting the pivot index at the beginning of the array.
const pivot = start;
// Placing the left index next to the pivot on the right.
let left = start + 1;
let right = end;
while (right >= left) {
if (array[left] > array[right] && array[right] < array[pivot])
swap(left, right, array);
if (array[left] < array[pivot]) left += 1;
if (array[right] > array[pivot]) right -= 1;
}
swap(pivot, right, array);
// Always sorting the smaller sub-array first
const leftIsSmaller = right - 1 - start < end - (right + 1);
if (leftIsSmaller) {
quickSort(array, start, right - 1);
quickSort(array, right + 1, end);
}
else {
quickSort(array, right + 1, end);
quickSort(array, start, right - 1);
}
}
function swap(a, b, array) {
[array[a], array[b]] = [array[b], array[a]];
return array;
}
Analysing the Big O notation:
- Worst case: Time = O(n^2) due to repetitive swapping of pivot to the end of the unsorted part, leading to O(n*n) complexity
- Best case: Time = O(nlog(n)) when the pivot divides the array into two equal halves
- Average case: Time = O(nlog(n))
- Space complexity = O(log(n)) because of recursive calls with two sub-arrays and prioritizing quicksort on the smaller sub-array
The other algorithm didn't exceed LeetCode's time limit and surprisingly, it showcased significantly better performance than most submissions. Although having two while loops nested within the main loop, it proved to be more efficient than perceived.
function quickSort(array) {
sortHelper(array, 0, array.length - 1);
return array;
}
function sortHelper(array, start, end) {
if (start >= end) return;
let i = start;
let j = end;
let base = array[i];
while (i < j) {
while (i < j && array[j] >= base) j -= 1; // This step makes sense but its timing priority raises questions
array[i] = array[j]; // Questioning the need for this line
while (i < j && array[i] <= base) i += 1;
array[j] = array[i]; // and this line. Aren't these lines risking loss of access to array values?
}
array[i] = base;
sortHelper(array, start, i - 1);
sortHelper(array, i + 1, end);
}
The disparity in performance between the algorithms leaves me questioning the reasons behind such outcomes.