SearchingAlgorithmaka Hoare's selection algorithm, k-th smallest element, selection by partition

Quickselect

Find the k-th smallest element in expected O(n) by partitioning like quicksort but recursing into only one side.

▶ VisualizePattern: Two PointersPractice (3)
Progress

Overview

Quickselect answers "what is the k-th smallest element?" (median, top-k boundary, percentile) in expected `O(n)` time without sorting. It borrows Quick Sort's Partitioning step: pick a pivot, move smaller elements left and larger right, then look at where the pivot landed. If it landed at index k, done; otherwise recurse into only the side that contains index k.

Because only one side is processed, the work is n + n/2 + n/4 + … = 2n on average, instead of quicksort's n log n. The worst case is O(n²) with bad pivots; random pivots make that vanishingly unlikely, and the median-of-medians pivot rule guarantees O(n) at a high constant cost. C++'s std::nth_element is an introselect (quickselect with a fallback).

k-th elementpartitionexpected O(n)in-placeorder statistics

Intuition

A mental model before the formal terms.

You want the 10th-tallest person in a crowd of 100. Pick someone at random, and have everyone shorter stand on their left and everyone taller on their right. If exactly 9 people are on their left, they are the answer. If 30 are on their left, the answer is among those 30 — ignore the other 70 completely and repeat. Each round throws away a large fraction of the crowd.

How it works

  1. Work on the range [lo, hi] with target index k (0-based, in the whole array).
  2. Pick a pivot — a random index is the standard choice — and swap it to hi.
  3. Lomuto partition: walk j from lo to hi - 1, swapping a[j] to position i (and incrementing i) whenever a[j] < pivot. Finally swap the pivot into i; it is now at its final sorted position p.
  4. If p == k, return a[p]. If k < p, repeat on [lo, p - 1]; otherwise repeat on [p + 1, hi].

Why it works

After partitioning, the pivot is at index p with all elements in [lo, p) ≤ pivot and all in (p, hi] ≥ pivot. That is exactly the position it would have in the sorted array, so if p == k the pivot is the k-th smallest.

If k ≠ p, the k-th smallest lies entirely within one side, and the other side can never change its relative rank — discarding it is safe.

With a uniformly random pivot, the expected surviving range after one partition is at most 3n/4, giving a geometric series and expected O(n) total work.

Recognition

How to tell a problem wants this.

  • The problem asks for the k-th largest/smallest, the median, or a top-k set without requiring the top-k in sorted order.
  • n up to 10^5–10^6 and a single query — sorting (O(n log n)) works but the interviewer asks "can you do better?"
  • Space must be O(1) extra, ruling out a heap of size k for large k.
“sorted array” → Two Pointers“k most frequent” → Heap / Priority Queue“merge k sorted” → Divide and Conquer

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
↑lo
10
1
14
2
37
3
13
4
5
5
42
6
21
7
↑hi
1/31Find the 4-th smallest element (0-based rank k=3) without fully sorting. Like quick sort, but after each partition only the side containing rank k is kept.
PivotComparing with pivotSwappedLess than pivotk-th smallestEliminated
PseudocodeLearn Quickselect →
1lo = 0, hi = n - 1, k = k - 1   # 0-based rank
2while lo <= hi:
3  pivot = a[hi]; i = lo
4  for j in lo .. hi-1:
5    if a[j] < pivot: swap(a[i], a[j]); i += 1
6  swap(a[i], a[hi])
7  if i == k: return a[i]
8  if k < i: hi = i - 1
9  else: lo = i + 1
Variables
k3
lo0
hi7
Complexity
best O(n)
avg O(n)
worst O(n²)
space O(1)
Speed

Pseudocode

1select(a, lo, hi, k):
2  if lo == hi: return a[lo]
3  p = partition(a, lo, hi, randomPivot(lo, hi))
4  if k == p: return a[p]
5  if k < p: return select(a, lo, p - 1, k)
6  return select(a, p + 1, hi, k)

Implementations

1import heapq
2import random
3from typing import Callable, TypeVar
4 
5T = TypeVar("T")
6 
7 
81 · Lomuto partition around a chosen pivot; returns the pivot final index
9def partition(a: list[int], lo: int, hi: int, pivot_index: int) -> int:
10    pivot = a[pivot_index]
11    a[pivot_index], a[hi] = a[hi], a[pivot_index]  # park the pivot at the end
12    store = lo
13    for i in range(lo, hi):
14        if a[i] < pivot:
15            a[i], a[store] = a[store], a[i]
16            store += 1
17    a[store], a[hi] = a[hi], a[store]  # put the pivot in its final place
18    return store
19 
20 
212 · Iterative quickselect: recurse into one side only, never both
22def quickselect(a: list[int], k: int) -> int:
23    # k is 0-based
24    if not 0 <= k < len(a):
25        raise IndexError("k out of range")
26    lo, hi = 0, len(a) - 1
27    while lo < hi:
28        p = partition(a, lo, hi, random.randint(lo, hi))
293 · Discard the half that cannot contain rank k
30        if p == k:
31            return a[k]
32        if p < k:
33            lo = p + 1
34        else:
35            hi = p - 1
36    return a[k]
37 
38 
394 · heapq covers the small-k case in O(n log k) without mutating the input
40def kth_smallest_by_heap(a: list[int], k: int) -> int:
41    return heapq.nsmallest(k + 1, a)[k]
Walkthrough
  1. The tuple swap a[i], a[store] = a[store], a[i] needs no temporary and is a single evaluate-then-assign step.
  2. random.randint(lo, hi) is inclusive on both ends, which matches the partition range exactly.
  3. if not 0 <= k < len(a) uses a chained comparison to express the range check in one readable line.
  4. The while lo < hi loop avoids recursion entirely, so there is no interaction with CPythons 1000-frame recursion limit.
  5. heapq.nsmallest(k + 1, a)[k] is the non-mutating alternative — O(n log k), and usually the right call for small k.
Complexity (this implementation)
time O(n) expected, O(n²) worst case · space O(1) for quickselect, O(k) for the heap variant

Python-level loops are slow enough that sorted(a)[k] (C-level TimSort) beats this quickselect for n well into the hundreds of thousands.

Language notes
  • Python has no nth_element; heapq.nsmallest/nlargest and sorted are the practical selection tools, and statistics.median handles the common special case.
  • heapq.nsmallest(k, it) switches strategy internally: for k close to n it just sorts, for small k it maintains a heap of size k.
  • random.randint(a, b) is inclusive of b, unlike random.randrange(a, b) — a frequent off-by-one when porting.
  • sorted() returns a new list while list.sort() sorts in place; quickselect here is in the second camp and should be documented as such.
Common mistakes in this language
  • Using random.randrange(lo, hi) and never selecting hi as a pivot, which biases the partition and is a silent correctness-preserving performance bug.
  • Recursing instead of looping and hitting RecursionError on large adversarial inputs where the partition is repeatedly unbalanced.
  • Calling heapq.nsmallest(k, a)[k] with an off-by-one — the k-th smallest 0-based needs nsmallest(k + 1, a)[k].
Language differences that matter here
  • Library support: C++ has std::nth_element (guaranteed O(n) via introselect) and std::partial_sort; Python has heapq.nsmallest/nlargest; JavaScript and TypeScript have neither, so the hand-rolled version is the only option.
  • Random range conventions differ: std::uniform_int_distribution(lo, hi) and random.randint(lo, hi) are inclusive, while Math.random() needs the lo + floor(rand * (hi - lo + 1)) idiom and random.randrange is exclusive.
  • Default sort behaviour: JavaScript sort() compares stringified values unless given a comparator, which makes the "just sort it" fallback silently wrong on numbers — the only language here with that trap.
  • Recursion limits: a recursive quickselect can raise RecursionError in Python at ~1000 frames, while C++ and JS/TS simply grow the stack until it overflows; the iterative form sidesteps all of it.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n²)
Space
O(1)

Worst case needs adversarial pivots; median-of-medians pivot selection guarantees O(n). Iterative version uses O(1) extra space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • k-th smallest/largest, median, or percentile of an unsorted array in one shot.
  • Top-k selection when the top-k need not be sorted: after selecting, a[0..k) are the k smallest.
  • Memory-constrained situations — it works in place, unlike a heap of size k or a sorted copy.
Avoid it when
  • Streaming data or many incremental queries — a Binary Heap of size k (O(n log k)) or two heaps for a running median fit better.
  • You need the top-k in order — quickselect then sort the prefix, or just use a heap.
  • Strict worst-case guarantees on adversarial input without random pivots — use median-of-medians or a heap.
  • Input must not be mutated and you cannot afford a copy.

Alternatives

Quick SortBinary HeapPriority QueueMerge Sort

Common mistakes

  • Mixing 0-based and 1-based k ("k-th largest" = index n - k when selecting smallest, 0-based).
  • Using the first element as pivot; sorted or reverse-sorted input then degrades to O(n²).
  • Recursing into both sides — that is quicksort, O(n log n).
  • Off-by-one in partition when elements equal the pivot; with many duplicates prefer 3-way partitioning.

Interview patterns

  • Kth largest element in an array: quickselect on index n - k.
  • Top-k frequent elements: quickselect over (count, value) pairs after a hash count.
  • K closest points to origin: quickselect on squared distance.
  • Median of an array in O(n), and the weighted-median variant for minimizing total moves.
Interview questions on this
Mock interviews

Example problems

Sort Colors (Dutch National Flag)mediumKth Largest Element in an ArraymediumTop K Frequent Elementsmedium