64
34
25
12
22
11
90
0
1
2
3
4
5
6
Starting Quick Sort. We pick a pivot and partition around it.
Presets:
Size:
Timeline Progress:
0%Step 1 / 32
Comparisons
0
Swaps / Actions
0
Speed:
Shortcuts: Space Play ā¢ ā/ā Step ā¢ R Reset ā¢ M Sound ā¢ Z Focus
Implementation Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
return arr;
}
function partition(arr: number[], low: number, high: number): number {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}Complexity Analysis
Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(nĀ²)
Space
O(log n)
Color Legend
Unsorted
Comparing
Swapping
Sorted
Quick Sort is a highly efficient divide-and-conquer algorithm. It selects a "pivot" element and partitions the other elements into two groups ā those less than the pivot and those greater. It then recursively sorts each group. With a good pivot strategy (like the median-of-three), it achieves O(n log n) average performance and is typically the fastest in-place sorting algorithm in practice.