Quickselect , K-th in Linear Time

The problem

"Find the K-th smallest element in an unsorted array." (Or K-th largest; symmetric.) The naïve approach is sort then index. O(n log n). Quickselect achieves O(n) expected.

This problem appears constantly: median computation (K = n/2), top-K selection (run quickselect for the K-th, then partition around it), kth-distance queries, robust statistics. Whenever you find yourself sorting just to look up one position, quickselect is the right tool.

The partition step

Choose a pivot from the array. Rearrange the array in-place so that all elements less than the pivot are on the left, all greater on the right, and the pivot sits at its final sorted position. The standard Lomuto partition:

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i                                            # final index of the pivot

After partition, a[lo..i) are all less than pivot, a[i] == pivot, and a[i+1..hi] are all ≥ pivot. The pivot is now in its sorted position.

The select loop

import random

def quickselect(a, k):
    """Return the k-th smallest element (0-indexed)."""
    lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        # Random pivot to avoid pathological worst cases.
        p = random.randint(lo, hi)
        a[p], a[hi] = a[hi], a[p]
        idx = partition(a, lo, hi)
        if idx == k:
            return a[idx]
        elif idx < k:
            lo = idx + 1                                # k-th is in the right half
        else:
            hi = idx - 1                                # k-th is in the left half

The algorithm is iterative, recursion isn't needed because we only ever descend into one half, so the call stack is wasted. Each iteration partitions and either returns the answer or shrinks the range to one of the two halves.

Complexity, reasoned

The partition is O(hi - lo + 1) per call. After each partition, we recurse on one of the two halves. With a random pivot, the expected size of the half containing the K-th element is about 3n/4 (the pivot is uniformly random, so on average the K-th lies in the larger half).

The geometric sum n + 3n/4 + (3/4)²n + … converges to 4n. So expected total work is O(n). Variance is large but bounded; with high probability a single run is within a small constant of expected.

Worst case: the pivot is always the smallest or largest element. Each partition removes one element instead of half. Total work O(n²). Random pivots make this exponentially unlikely; median-of-medians (below) eliminates it deterministically at the cost of constant factors.

Median-of-medians (deterministic linear)

If you must guarantee O(n) without probability, choose the pivot using the median-of-medians algorithm. Group elements into chunks of 5, find each chunk's median, then recursively find the median of those medians, that's the pivot. The recursion is on n/5 elements, plus the partition on n elements; the total is bounded by T(n) = T(n/5) + T(7n/10) + O(n), which solves to O(n).

Constant factors are large. Most practical implementations use random pivots and accept the O(n²) worst case (which essentially never occurs). Median-of-medians is worth knowing exists; rarely the right choice in production code.

Where quickselect appears in practice

Top-K problem

"Return the K largest elements of an array." Run quickselect for position n − k. Now everything to the right is the top K (in unsorted order). Partition once more if the order matters. Total: O(n) expected.

Beats heap-of-K (O(n log k)) when the array fits in memory and modifications are allowed. Fails for streams; heap is the right tool when elements arrive one at a time.

Median in O(n)

Run quickselect for k = n/2 (or k = n/2 - 1 and n/2 averaged for even-length arrays). Beats sort-then-pick.

Standard-library equivalents

• C++: std::nth_element(begin, kth, end) rearranges so the K-th element is in place; everything to its left is <, everything to its right is ≥.
• Python: heapq.nsmallest(k, iterable) for K small; for large K, sorted(...)[:k] is fine. There's no direct quickselect in the standard library.
• Java: No standard quickselect; Arrays.sort + index, or implement.

Three-way partition for many duplicates

Standard partition is sensitive to duplicates, if many elements equal the pivot, they all end up on one side and the partition becomes unbalanced. The fix is the three-way (Dutch flag) partition: split into less-than, equal, greater regions.

See the Dutch National Flag deep-dive for the full implementation. The advantage: arrays with many duplicates partition into smaller sub-problems, making quickselect more robust.

When NOT to use quickselect

• Streaming data. Quickselect needs random access. For streams use a heap.
• You need the answer plus everything sorted. Just sort. Two-pass approaches are slower.
• Hard real-time guarantees. Worst-case O(n²) (rare but possible). Use median-of-medians or accept the risk.
• The K-th element matters multiple times for different K. One sort serves all queries; multiple quickselects don't share work.

Where beginners go wrong

• Choosing the first or last element as pivot without randomisation. On sorted or reverse-sorted input, pivots are always extremal. O(n²) worst case triggered every time. Randomise.
• Recursing into both halves. That's quicksort. Quickselect descends only into the half containing the K-th element.
• Off-by-one on K. 0-indexed vs 1-indexed K is a common source of bugs. Pick a convention; document it.
• Using two-way partition on arrays with many duplicates. The partition becomes unbalanced; runtime degrades. Three-way partition is more robust.
• Forgetting that the array is mutated. Quickselect rearranges the input. If you need the original order, copy first.

What to read next

The Dutch National Flag piece covers three-way partitioning. The Sorting & Search module ties quickselect to quicksort and other comparison sorts. Heap as Array Arithmetic covers the streaming-friendly alternative.