Quickselect for the k-th element

Quickselect finds the k-th smallest value of an unsorted array, such as its median, in expected O(n) time and without sorting it. It partitions the array around a pivot the way quicksort does, which leaves the pivot at the position it would have in sorted order, and then keeps only the side that holds position k: the other side is never looked at again. C. A. R. Hoare published it as FIND, Algorithm 65 of the Communications of the ACM. A random pivot keeps the expected work linear on every input, and a three-way partition keeps repeated values cheap. This lesson’s problem asks for the median income of a large survey.

The problem: the median household income

1. [42000, 18000, 95000, 27000, 61000] with k = 3 gives 42000, the middle of the five.
2. [30000, 30000, 30000, 12000] with k = 2 gives 30000: repeats count, so the second smallest is a copy of 30000.
3. [7] with k = 1 gives 7.

The brute force: take out the minimum k times

Remove the smallest value, k times, and the last one removed is the answer. Each removal scans what is left, so the median of n values costs about 3n²/8 steps. Sorting the whole survey and reading one position is the usual shortcut, and the run counts what it pays for:

# The k-th smallest income by brute force: take out the smallest value k times. Then the cost of sorting instead.
import random


def kth_by_repeated_minimum(values, k):
    """Removes the minimum k times; returns the last one removed and the number of values looked at."""
    rest = list(values)
    looked = 0
    for _ in range(k):
        looked += len(rest)
        smallest = min(rest)
        rest.remove(smallest)
    return smallest, looked


for incomes, k in (([42000, 18000, 95000, 27000, 61000], 3), ([30000, 30000, 30000, 12000], 2), ([7], 1)):
    print(f"{incomes}, k = {k} -> {kth_by_repeated_minimum(incomes, k)[0]}")

rng = random.Random(5)
survey = [rng.randint(5_000, 400_000) for _ in range(2_001)]
_, looked = kth_by_repeated_minimum(survey, 1_001)
print(f"median of 2,001 incomes: {looked:,} values looked at")
n = 1_000_001
print(f"median of {n:,} incomes: {(n + (n - 500_000)) * 500_001 // 2:,} values to look at")


class Counted:
    """An income that counts how often sorted() compares it (sorted() only uses <)."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.value < other.value


sorted(Counted(rng.randint(5_000, 400_000)) for _ in range(100_001))
print(f"sorting 100,001 incomes to read one of them: {Counted.comparisons:,} comparisons")

[42000, 18000, 95000, 27000, 61000], k = 3 -> 42000
[30000, 30000, 30000, 12000], k = 2 -> 30000
[7], k = 1 -> 7
median of 2,001 incomes: 1,502,501 values looked at
median of 1,000,001 incomes: 375,001,250,001 values to look at
sorting 100,001 incomes to read one of them: 1,531,912 comparisons

For 2,001 incomes the median took 1,502,501 values looked at, and for a million incomes it would take about 3.75 × 10¹¹, far beyond any time limit. Sorting 100,001 incomes made 1,531,912 comparisons, an O(n log n) bill for a question about one position: the order of the other 100,000 incomes was never asked for.

What to notice

Only one position of the sorted order matters. A partition around any pivot puts the pivot exactly where a full sort would, with every smaller value before it and every larger value after it, so after one pass you know on which side the answer lies and can drop the other side whole.

Quickselect, step by step Pro: opens with a Pro, Premium or Ultimate pass