Loading...
A highly efficient divide-and-conquer algorithm that picks a pivot element and partitions the array around it. Generally performs better than other O(n log n) algorithms in practice.
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
// Partition the array and get pivot index
const pivotIndex = partition(arr, left, right);
// Recursively sort left and right partitions
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
function partition(arr, left, right) {
const pivot = arr[right]; // Last element as pivot
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] <= pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
// Place pivot in correct position
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
// Time: O(n log n) average, O(n²) worst
// Space: O(log n) recursion stackfunction medianOfThree(arr, left, right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < arr[left]) {
[arr[left], arr[mid]] = [arr[mid], arr[left]];
}
if (arr[right] < arr[left]) {
[arr[left], arr[right]] = [arr[right], arr[left]];
}
if (arr[mid] < arr[right]) {
[arr[mid], arr[right]] = [arr[right], arr[mid]];
}
return right; // Median is now at right
}function quickSortIterative(arr) {
const stack = [[0, arr.length - 1]];
while (stack.length > 0) {
const [left, right] = stack.pop();
if (left >= right) continue;
const pivotIndex = partition(arr, left, right);
// Push smaller partition first (optimization)
if (pivotIndex - left < right - pivotIndex) {
stack.push([pivotIndex + 1, right]);
stack.push([left, pivotIndex - 1]);
} else {
stack.push([left, pivotIndex - 1]);
stack.push([pivotIndex + 1, right]);
}
}
return arr;
}Pivot always divides array into two equal halves. Tree depth is log n, each level requires n comparisons.
Random pivot selection gives good partitions on average. Expected depth is log n with high probability.
Pivot is always smallest or largest element (sorted arrays with first/last pivot). Tree depth becomes n.