SearchingSearching

Quickselect (k-th smallest)

Find the k-th smallest element in expected O(n) by partitioning like quicksort but recursing into only one side.

Array | k — Numbers, then a pipe, then k (1-based rank of the smallest element to find) — e.g. "7, 2, 9, 4 | 2"

↑lo

↑hi

1/31Find the 4-th smallest element (0-based rank k=3) without fully sorting. Like quick sort, but after each partition only the side containing rank k is kept.

PivotComparing with pivotSwappedLess than pivotk-th smallestEliminated

PseudocodeLearn Quickselect →

1lo = 0, hi = n - 1, k = k - 1   # 0-based rank
2while lo <= hi:
3  pivot = a[hi]; i = lo
4  for j in lo .. hi-1:
5    if a[j] < pivot: swap(a[i], a[j]); i += 1
6  swap(a[i], a[hi])
7  if i == k: return a[i]
8  if k < i: hi = i - 1
9  else: lo = i + 1

Variables

lo0

hi7

Complexity

best O(n)

avg O(n)

worst O(n²)

space O(1)

Speed