Quick Sort
MediumPartition around a pivot
Pick one number, put smaller ones on its left and bigger ones on its right, then do the same trick on each side.
The idea
Choose a pivot and partition the array so smaller values go left and larger go right; the pivot is then in its final place. Recurse on each side. Fast and in-place on average.
The trick
- After a partition, the pivot never moves again — its position is final.
7
2
1
6
8
5
3
0
1
2
3
4
5
6
Step 1 of 21. Pick a pivot, partition smaller values to its left and larger to its right, then sort each side. Values: 7, 2, 1, 6, 8, 5, 3.
1/21
Optimal
timeO(n log n)spaceO(log n)
In-place, cache-friendly.
1// partition around a pivot, then sort each side2function quick(lo, hi) {3 if (lo >= hi) return;4 const pivot = a[hi];5 let i = lo;6 for (let j = lo; j < hi; j++)7 if (a[j] < pivot) swap(i++, j);8 swap(i, hi);9 quick(lo, i - 1);10 quick(i + 1, hi);11}Input
- array
- [7, 2, 1, 6, 8, 5, 3]
Memory
- pivot
- —
- i
- —
- j
- —
- piv
- —
Output
- result
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [10, 7, 8, 9, 1, 5]
- Output:
- [1, 5, 7, 8, 9, 10]
- Explanation:
- Partition around a pivot, then recurse.
Example 2
- Input:
- nums = [3, 1, 2]
- Output:
- [1, 2, 3]
- Explanation:
- Small values go left of the pivot, big ones right.
Example 3
- Input:
- nums = [2, 2, 1]
- Output:
- [1, 2, 2]
- Explanation:
- Duplicates are handled fine.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.