Quickselect

Sometimes you need only one value from the sorted order, such as the median or the tenth smallest. Sorting everything costs O(n log n). Quickselect finds it in O(n) on average, by partitioning and then keeping only the side that holds the answer.

The k-th smallest

Given a list and a position k (counting from 0), find the value that would be at index k if the list were sorted. For k = 0 that is the minimum, which one pass finds. For the median, k = n // 2, there is no such shortcut.

Partition, then keep one side

Partition around a pivot, as in lesson 3. The pivot lands at its final index p. If p = k, the pivot is the answer. If k < p, the answer is among the values to the left; otherwise it is to the right. Unlike quick sort, only one side is searched again.

Keep the range a[lo..hi] that must hold the answer. Pick a random pivot in it and partition the range (lesson 3); the pivot lands at index p. Then one round narrows the range:

if p == k:
    return a[p]
if k < p:
    hi = p - 1
else:
    lo = p + 1

Repeat until the pivot lands at k. Writing the whole method, without changing the input, is SORT-P4.

Why it is O(n) on average

With a random pivot, the pivot lands in the middle half of the range at least half the time. When it does, at most three quarters of the range is kept. So on average, every two rounds shrink the range to at most three quarters of its size. A round costs at most the size of its range. The total is at most 2 × (n + (3/4)n + (3/4)²n + …), where (3/4)² is 3/4 × 3/4. Each term is three quarters of the one before, so the sum in brackets stays below 4n, and the total below 8n. That is O(n) expected time.

The worst case, with very unlucky pivots, is still O(n²). A method called “median of medians” picks a pivot that is always good enough, giving O(n) in the worst case. It is slower in practice and rarely used, but it proves that selection really is easier than sorting.

Many equal values

If the list is a million copies of the same value, Lomuto’s partition puts all of them on one side every time, and quickselect takes O(n²). Use a three-way partition: less than, equal to, and greater than the pivot. If k falls in the equal part, the answer is the pivot, and you stop.

Other ways

• Sort and index: sorted(a)[k]. O(n log n), but simple and often fast enough.
• A heap of size k + 1: keep the k + 1 smallest seen so far. O(n log k), and it works on a stream of values that does not fit in memory. heapq.nsmallest(k + 1, a)[-1] does this.

Now try SORT-P4, The k-th fastest.