0

Quick Sort

Medium

Pick a pivot, partition everything smaller to its left and larger to its right, then recurse on both sides.

divide and conquerin placeunstable
TimeO(n log n) average, O(n^2) worst
SpaceO(log n) stack
InputComma separated numbers
10
0
80
1
30
2
90
3
40
4
50
5
70
6

Partition around a pivot, then recurse into both sides.

comparisons0swaps0
1 / 37
quick(lo, hi):
if lo >= hi: return
p = partition(lo, hi)
quick(lo, p-1); quick(p+1, hi)
partition: pivot = a[hi]; i = lo
for j in lo..hi-1: if a[j] < pivot: swap(a[i++], a[j])
swap(a[i], a[hi]); return i
Why it matters

Fastest in practice because it sorts in place with excellent cache behaviour. Randomise the pivot to dodge the worst case.

Practise this
Kth Largest Element in an ArrayMSort ColorsM
Keyboard
space play← → stepr restartctrl K search

More in Sorting

Quickselect
O(n) expected, O(n^2) worst
Bubble Sort
O(n^2), best O(n) when already sorted
Selection Sort
O(n^2) always
Insertion Sort
O(n^2), O(n) on nearly sorted input
Merge Sort
O(n log n) always
Counting Sort
O(n + k)
Next visualiser
Heap Sort