Quickselect and Top-K Selection

Finding the median of a million numbers doesn't require sorting all million of them — full sorting throws away the fact that you only wanted one specific position in the order, not the whole order. Quickselect finds the $k$-th smallest element directly, in average $O(n)$ time, by borrowing quicksort's partition step but discarding the half of the work a full sort would do.

The idea: partition, then recurse into only one side

Quicksort partitions an array around a pivot — everything smaller goes left, everything larger goes right — then recursively sorts both sides. Quickselect partitions the same way, but after partitioning it knows exactly which side the $k$-th element must be in (by comparing $k$ to the pivot's final position), so it recurses into only that one side and ignores the other completely.

That single change is what drops the average complexity from quicksort's $O(n \log n)$ to quickselect's $O(n)$: each partition step costs $O(n)$, but the next call operates on roughly half the data, giving $n + n/2 + n/4 + \dots \approx 2n = O(n)$ — a geometric series that sums to a constant multiple of $n$, instead of quicksort's $\log n$ full passes over shrinking-but-still-both-sides subarrays.

Worked example: 3rd smallest of [7, 2, 9, 4, 1, 8]

Looking for $k=3$ (1-indexed), pivot on the last element, 8:

• Partition around 8: everything is smaller (8 is the max), so it lands at index 5. Values left of it: [7, 2, 9, 4, 1] in some order — index 5 means 8 is the 6th smallest. Since $3 < 6$, recurse into the left part only, discarding 8 and the right side entirely (here, nothing).
• New array [7, 2, 9, 4, 1], still looking for the 3rd smallest overall. Pivot on 1 (last element): everything else is larger, so 1 lands at index 0 — the 1st smallest. Since $3 > 1$, recurse into the right part, now looking for the $3-1=2$nd smallest of [7, 2, 9, 4].
• Pivot on 4 (last element): [2] smaller, [7, 9] larger, so 4 lands at index 1 — the 2nd smallest of this subarray. That's exactly $k=2$ — done. Answer: 4.

Check by full sort: [1, 2, 4, 7, 8, 9] — the 3rd smallest is indeed 4. Quickselect found it after touching each remaining subarray once, never sorting the discarded half.

import random

def quickselect(arr, k):                 # k-th smallest, 0-indexed, avg O(n)
    pivot = random.choice(arr)
    lows  = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]

    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivot                      # k lands inside the pivot block
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

Where it shows up

Interviewers ask for "kth largest element," "top k frequent elements," or median-finding, and the expected answer contrasts quickselect's average $O(n)$ against sorting's $O(n \log n)$ or a heap's $O(n \log k)$ — and knowing which to reach for depending on whether $k$ is small or you need the result repeatedly. In quant work, this is the algorithm behind picking the top-decile names in a cross-sectional signal, finding the median of a rolling window without a full sort, or computing a VaR percentile from a large simulated P&L distribution without sorting the whole array first.