What you'll learn
Sometimes you don't need the whole array sorted — just the k-th smallest element, or the median. Quickselect finds it in expected O(n), and a clever pivot rule makes that guarantee hold even in the worst case.
By the end you'll be able to:
- State the selection problem
- Run quickselect and analyze its expected
O(n) - Explain median of medians for worst-case linear time
The selection problem
Given an unsorted array, find the element that would sit at sorted index k — the k-th order statistic. The median is just k = n/2. You could sort (O(n log n)) and index, but selection can be done in linear time — you don't need the other elements ordered.
Quickselect
Quickselect is quick sort that only recurses into the side containing k. Partition around a pivot; the pivot lands at some index p. If p == k you're done. If k is on one side, recurse there and ignore the other half entirely — that's the saving:
Because each step throws away (on average) half the array, the work is n + n/2 + n/4 + … ≈ 2n — an expected O(n), not O(n log n).
In code
def quickselect(a, k): # k-th smallest, 0-indexed
lo, hi = 0, len(a) - 1
while lo < hi:
p = partition(a, lo, hi)
if p == k: return a[k]
elif p < k: lo = p + 1 # answer is on the right
else: hi = p - 1 # answer is on the left
return a[k]
def partition(a, lo, hi):
pivot = a[hi]; i = lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]; i += 1
a[i], a[hi] = a[hi], a[i]
return iWatch out
O(n²) (imagine peeling off one element at a time). Randomizing the pivot makes that astronomically unlikely — the expected time stays O(n).Guaranteed linear time
To remove the worst case entirely, the median-of-medians algorithm chooses a provably good pivot: split the array into groups of five, take each group's median, then (recursively) take the median of those medians. That pivot always discards a constant fraction of the array, giving worst-case O(n).
Key idea
O(n) selection — but its constant factor is large, so randomized quickselect is what you actually use in practice.Complexity
| Method | Expected | Worst case | Space |
|---|---|---|---|
Sort then index | O(n log n) | O(n log n) | O(1)–O(n) |
Quickselect | O(n) | O(n²) | O(1) |
Randomized quickselect | O(n) | O(n²) (rare) | O(1) |
Median of medians | O(n) | O(n) | O(log n) |
Recap & quick check
Key takeaways
- Selection finds the k-th smallest element without fully sorting.
- Quickselect partitions and recurses into only the side holding k — expected O(n).
- A bad pivot makes quickselect O(n²); randomizing the pivot fixes it in practice.
- Median of medians picks a provably good pivot for worst-case O(n).
- The median is selection with k = n/2.
Quick check
1. What is the expected time of quickselect?
2. How does quickselect differ from quicksort?
3. What does median-of-medians guarantee?
4. Finding the median is selection with which k?
Quickselect and both fast sorts share one strategy. Let's make that strategy explicit. Next up: Module 11 — The Divide & Conquer Paradigm.