0

Quickselect

Medium

Partition around a pivot, then recurse only into the side that contains the rank you want.

partitionexpected linear
TimeO(n) expected, O(n^2) worst
SpaceO(1)
Inputnumbers | k for the kth smallest
3
0
4
1
7
2
10
3
15
4
20
5
target2

Looking for the 3th smallest value, which lives at final index 2.

comparisons0
1 / 15
select(lo, hi, k):
p = partition(lo, hi)
if p == k: return a[p]
if p < k: select(p+1, hi, k)
else: select(lo, p-1, k)
Why it matters

Halving the work each time gives n + n/2 + n/4 ... which sums to 2n.

Practise this
Kth Largest Element in an ArrayMK Closest Points to OriginM
Keyboard
space play← → stepr restartctrl K search

More in Sorting

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
Quick Sort
O(n log n) average, O(n^2) worst
Counting Sort
O(n + k)
Next visualiser
Bubble Sort