The idea: partition, then keep one side

The k-th smallest element is the one that would sit at index k − 1 if the array were sorted. The median, the minimum (k = 1) and the 90th percentile are all k-th smallest questions. Sorting first works but costs O(n log n). Quickselect (Hoare, 1961) borrows quicksort's partition step and does far less: after each partition it keeps only one side, the side that holds index k − 1.

The array 5 2 3 10 4 8 1 7 9 6 partitioned around the pivot 6: the smaller values 5 2 3 4 1 on the left in blue, 6 at index 5 in orange, the larger values 10 7 9 8 on the right in red. The target index k − 1 = 4 is on the left, so the left side is kept and the pivot and right side are greyed out.
After one partition the pivot is in its sorted place; the answer lies on one side of it, so the other side is dropped.

Partition: the pivot finds its sorted place

The page uses Lomuto's partition with the last element as the pivot. An index j scans the range from left to right; i marks the end of the block of values smaller than the pivot. When a[j] is smaller, i moves one step and a[i] and a[j] swap. At the end the pivot swaps into index p = i + 1.

partition(a, lo, hi):
    pivot = a[hi]; i = lo - 1
    for j in lo .. hi-1:
        if a[j] < pivot: i = i + 1; swap a[i], a[j]
    swap a[i+1], a[hi]
    return i + 1

Now every value left of p is smaller than the pivot and every value right of it is not. So the pivot is exactly the (p + 1)-th smallest, even though neither side is sorted. In the canvas, blue cells are smaller than the pivot and red cells are not.

Pick a side

Compare p with the target index t = k − 1:

casemeaningnext range
p = tthe pivot is the answerstop
p > tthe answer is smaller than the pivot[lo .. p − 1], go left
p < tthe answer is larger than the pivot[p + 1 .. hi], go right

A range of one element is the answer without any comparison. Since only one side continues, quickselect is a plain loop, not a recursion with two calls. In 5 2 3 10 4 8 1 7 9 6 with k = 5, the pivot 6 lands at 5 (go left), then the pivot 1 lands at 0 (go right), then the pivot 5 lands at 4: found, after 16 comparisons. Quicksort of the same array makes 23. (Demo: median of 10) If the first pivot happens to land on t, one partition is enough. (Demo: lucky pivot) With k = n the answer is the maximum and every step goes right. (Demo: the largest) Equal values are fine: a value equal to the pivot counts as "not smaller" and goes right. (Demo: duplicates)

Why it is O(n) on average

A partition of m elements costs m − 1 comparisons. Quicksort partitions both halves, so every level of its recursion touches about n elements, and there are about log n levels: O(n log n). Quickselect follows only one half, so with pivots that split roughly in the middle the work is n + n/2 + n/4 + … ≈ 2n. With a random pivot the expected number of comparisons is at most about 4n (about 3.4n for the median): O(n) on average.

Two columns of shrinking bars for n = 16. Quicksort: four levels, each split into more pieces, every level 16 elements wide. Quickselect: bars of 16, 8, 4 and 2 elements, one per level, total about 2n.
Quicksort pays about n per level for log n levels; quickselect keeps one piece per level, so the total is about 2n.

The worst case and its fixes

The bad case is a pivot that splits off only one element. With the last element as pivot, a sorted array does that every time: the pivot is the largest value, lands at the end, and the range shrinks by one. For 1 … 10 and k = 1 that is 9 partitions and 9 + 8 + … + 1 = 45 comparisons, the same as quicksort's worst case: O(n²). (Demo: worst case) The usual fixes:

  • Random pivot: no fixed input is bad; O(n) expected, O(n²) only with tiny probability.
  • Median of three (first, middle, last): sorted and reversed input split well.
  • Median of medians (Blum, Floyd, Pratt, Rivest, Tarjan, 1973): pick the pivot as the median of the medians of groups of 5. It is guaranteed to split at least 30 / 70, so the worst case is O(n), but the constant is large.
  • Introselect: run quickselect, and switch to a guaranteed method if the range shrinks too slowly. This is what C++ std::nth_element does.

Where it is used

C++ std::nth_element, NumPy numpy.partition and numpy.median, and many "top k" routines are selection, not sorting. After quickselect the array is partitioned around the answer: the k − 1 values left of it are the k − 1 smallest (in no particular order). So the same call also gives the k smallest items. A heap of size k is the alternative for streams, at O(n log k).

See also Comparison Sorting, where quick sort uses the same partition on both sides, Quick Sort vs Merge Sort and Heap Sort vs Quick Sort for quicksort's sorted-input worst case, and Mean vs Median vs Mode for what a median is for.

Median of Medians picks a pivot from groups of 5 that is never bad, so selection is O(n) even in the worst case.

When the data arrives as a stream and cannot be held in memory, use a min-heap of size k instead: see Top-k with a Size-k Heap.

What the page leaves out

Inputs are capped at 10 whole numbers from 1 to 99 so the bars fit. The page uses only the last element as the pivot, so it does not animate random pivots, median of three, median of medians or introselect. It also leaves out Hoare's partition scheme (two pointers from both ends, fewer swaps), three-way partitioning for many equal values, the Floyd–Rivest sampling algorithm, and selection on data that does not fit in memory.