Quickselect: Partitioning to Find the k-th Smallest

Quickselect finds the k-th smallest item of an unsorted array, such as its median, by partitioning as quicksort does and then carrying on into only the side that holds the answer. This card traces it on seven numbers, shows why it takes O(n) time on average, and says when it does not.

After a partition the pivot sits at its final index p, the index it would have in the sorted array. The k-th smallest item belongs at index k − 1. If p is k − 1, the pivot is the answer. If k − 1 is less than p, the answer is among the items to the left, and everything on the right can be forgotten; if it is greater, the answer is on the right. Quickselect partitions again on that side alone, and stops when a pivot lands on index k − 1. It is quicksort with one of its two recursive calls removed, which turns a tree of calls into a single path.

To find the third smallest of 7 2 8 1 5 3 6, quickselect looks for the item that belongs at index 2. Each partition takes the last item of its range as the pivot. The trace marks the range still being searched with low and high, and the index where each pivot landed with pivot.

Two partitions found 3, which a check against the sorted array confirmed. The items 7 and 8 were compared once, in the first partition, and never again, and the array was never sorted: 2 and 1 are still out of order at the end. Only the part of the array that could hold the answer was worked on.

With pivots that land near the middle, the partitions cover n items, then about n/2, then about n/4, and so on. That sum stays below 2n, so with a random pivot the expected time is O(n), against O(n log n) for sorting the array and reading index k − 1. The worst case is the same as quicksort's, O(n²), when every pivot is the largest or smallest item of its range, and the remedy is the same random pivot.

Binary search is not quickselect, even though both discard part of the array at each step. Binary search needs the array sorted and looks for a known value; quickselect works on an unsorted array and looks for a value by its rank, which it cannot know until the partitions find it.

Reach for quickselect when you need one item by rank, a median, a percentile or the tenth highest score, and not the whole order. Python's statistics.median sorts its input first, which costs O(n log n), and C++ provides std::nth_element to do this job directly.