Quickselect

Cost and properties

average	~2n compares — linear
worst case	~n²/2
in place	yes
vs sorting	no n log n needed

Reference: Sedgewick & Wayne, §2.5; Hoare 1961.

Quickselect in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import random

def select(a, k):
    # Returns the kth smallest key (k = 0 is the minimum).
    random.shuffle(a)
    lo, hi = 0, len(a) - 1
    while hi > lo:
        j = partition(a, lo, hi)          # a[j] is now in its final place
        if j < k:
            lo = j + 1                    # answer is to the RIGHT
        elif j > k:
            hi = j - 1                    # answer is to the LEFT
        else:
            return a[k]                   # j == k: found it
    return a[k]

def partition(a, lo, hi):
    pivot = a[lo]
    i, j = lo, hi + 1
    while True:
        i += 1
        while i < hi and a[i] < pivot:
            i += 1
        j -= 1
        while j > lo and a[j] > pivot:
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
    a[lo], a[j] = a[j], a[lo]
    return j

Why it works

Why it is linear on average

Sorting recurs on both sides; selection recurs on one. With a random pivot the surviving range shrinks by about half each time, so the compares total n + n/2 + n/4 + … < 2n. Linear, not n log n — and the constant is small.

The three-way decision

After partitioning, a[j] is final. So compare j with k: if j < k the answer is strictly right of j; if j > k it is strictly left; if they are equal you are done. Notice the loop discards a whole side without sorting it. Watch the dimmed region grow — that is work never done.

Theory footnote

Worst case is still quadratic, and the shuffle is what makes that improbable. A guaranteed linear-time selection exists (median-of-medians, Blum–Floyd–Pratt–Rivest–Tarjan 1973) but its constant is so large that the randomised version wins in practice — a good example of the gap between an asymptotic guarantee and a fast program.

Where you need it

Medians and percentiles on large data, top-k queries, and as a subroutine when you need the kth element but not the order of the rest. Sorting to get one element is a common and expensive habit.

What to try in the animation

k is 0-based, so k = 4 asks for the 5th smallest. The median of 10 keys is k = 5.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• 5th smallest — keys: 7 10 5 3 8 4 2 9 6 1 · k: 4
• the minimum — keys: 7 10 5 3 8 4 2 9 6 1 · k: 0
• the median — keys: 7 10 5 3 8 4 2 9 6 1 · k: 5
• the maximum — keys: 7 10 5 3 8 4 2 9 6 1 · k: 9

Open Quickselect in the player →

The rest of Quicksort

• Quicksort Put one key where it belongs and everything smaller to its left.
• 3-way quicksort Partition into less-than, equal-to and greater-than.