Searching & Selection

Quickselect

Find the k-th smallest value without fully sorting — partition, then chase rank k into one side only.

The orange bar is the pivot; blue is the element being compared, purple the confirmed-smaller region. Discarded bars dim out; the green bar is the answer once the pivot lands on rank k.

What you're seeing

We want the k-th smallest element — the median, the 90th percentile, the 3rd-largest — but we don't need the whole array sorted to get it. Quickselect borrows quicksort's partition: pick a pivot, sweep the window moving every smaller element to the left, and the pivot drops into the exact slot it would occupy if the array were sorted. That slot's index is a rank. If it equals k, we're done. If not, rank k can only be on one side — so we throw the other side away and repeat. Unlike quicksort, we never recurse into both halves; we follow k.

The rule

select(a, k):                 # k-th smallest, 0-indexed
    lo, hi = 0, n-1
    while lo < hi:
        p = partition(a, lo, hi)   # pivot ends at its final sorted position p
        if   p == k: return a[p]
        elif p <  k: lo = p + 1    # rank k is to the right
        else:        hi = p - 1    # rank k is to the left
    return a[lo]

The invariant

The whole method rests on one fact about partitioning: after partitioning a window, the pivot sits at its final sorted position p — every element left of it is smaller, every element right of it is larger. So p is a true rank, with no need to sort either side. That immediately localizes the target: if p < k the k-th smallest must lie to the right (there are already p+1 elements ≤ the pivot), and if p > k it must lie to the left. Each round the live window keeps the invariant "rank k is somewhere in [lo, hi]," and shrinks; when it shrinks to a single cell, that cell is rank k. Correctness needs nothing probabilistic — the randomness only affects speed.

The cost

averageworstspace QuickselectO(n)O(n²)O(1) Sort then indexO(n log n)O(n log n)O(1)–O(n)

Because we recurse into only one side, the average work is n + n/2 + n/4 + … ≈ 2n — linear, beating the O(n log n) of sort-then-index. The worst case is O(n²) when pivots are consistently extreme (already-sorted input with a naive last-element pivot); a random pivot makes that astronomically unlikely, and the median-of-medians algorithm (Blum–Floyd–Pratt–Rivest–Tarjan, 1973) guarantees O(n) worst-case by choosing a provably good pivot — at the price of a larger constant, so introselect uses it only as a fallback.

In the wild

Selection is everywhere you need an order statistic without a full sort: std::nth_element in C++ and numpy.partition in Python are quickselect (introselect, with a median-of-medians fallback); it computes medians and percentiles for statistics and monitoring dashboards, finds the top-k by acting as the partition step that isolates them, and is the inner loop of median-based image filters and k-nearest-neighbor queries. Whenever you reach for "give me the k-th / the median / the top k," a full sort is usually overkill and this is the tool.

Try this

Set Rank k to 1 (the minimum) or n (the maximum) and watch the window march steadily from one end. Set it to the middle (the median) and notice how the window roughly halves each partition — that geometric shrink is the linear-time average. The discarded (dimmed) bars are work we provably never have to do.

References

  1. Hoare, C. A. R. "Algorithm 65: FIND." Communications of the ACM 4(7):321–322, 1961. The original.
  2. Blum, Floyd, Pratt, Rivest & Tarjan. "Time bounds for selection." Journal of Computer and System Sciences 7(4):448–461, 1973. Median-of-medians, worst-case O(n).
  3. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §9 (Medians and Order Statistics). MIT Press, 2022.