A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Quickselect finds the kth smallest element in O(n) average time by partitioning (like quicksort) but recursing on only the relevant partition. The Median-of-Medians algorithm guarantees O(n) worst-case time but with a large constant factor, making quickselect preferable in practice.
Implement quickselect and compare to sorting then indexing. Observe average-case performance and analyze how the algorithm avoids sorting unused partitions. Study Median-of-Medians to understand worst-case linear-time selection.
The selection problem asks: given an unsorted array of n elements, find the kth smallest without sorting the entire array. The naive approach — sort first, then index — costs O(n log n). But sorting does far more work than necessary. You don't need every element in order; you only need to know which single element belongs at position k. Quickselect exploits this insight to solve the problem in O(n) average time.
Quickselect reuses the partitioning step from quicksort, which you already know. Pick a pivot, partition the array so that elements smaller than the pivot are on the left and larger elements are on the right, and the pivot lands in its final sorted position. Now compare k to the pivot's position. If k equals the pivot's index, you're done — the pivot is the answer. If k is smaller, the kth element must be in the left partition; if k is larger, it must be in the right partition. Here is the key difference from quicksort: you only recurse into one side. Quicksort recurses into both partitions to sort everything; quickselect throws away the irrelevant half. This single-sided recursion is what drops the average cost from O(n log n) to O(n) — each level of recursion processes roughly half as many elements as the previous one, so the total work forms a geometric series that sums to O(n).
The catch is the same as quicksort's: pivot choice matters. A consistently bad pivot (always the largest or smallest element) degrades quickselect to O(n²). Randomized pivot selection makes this astronomically unlikely in practice, giving expected O(n) performance. For guaranteed worst-case O(n), the Median-of-Medians algorithm chooses a pivot by dividing the array into groups of five, finding each group's median, and recursively selecting the median of those medians. This guarantees a balanced-enough partition — at least 30% of elements on each side — ensuring linear time. However, the constant factor is roughly 5-10x larger than randomized quickselect, so Median-of-Medians is primarily of theoretical importance. In practice, randomized quickselect is the standard choice.
Selection algorithms appear wherever you need order statistics without full sorting: finding the median for robust statistics, computing percentiles in streaming data, selecting the kth-closest point in nearest-neighbor searches, or partitioning data for load balancing across servers. The `std::nth_element` function in C++ and `numpy.partition` in Python both implement quickselect variants internally.