Quickselect

Quickselect is the selection algorithm derived from Quicksort’s partition step, originally published by Tony Hoare in 1961 (CACM 4.7) under the name FIND — predating his quicksort paper by a year. Given an unsorted array of n elements and an index k, quickselect returns the element that would occupy index k in the sorted version of the array (the k-th order statistic) in O(n) expected time, without ever fully sorting the array. The algorithm is O(n²) in the worst case (with adversarial pivot selection), but with randomized pivots the worst case occurs only with vanishingly small probability and the expected time is provably linear via the recurrence T(n) = T(n / 2) + O(n), which solves to T(n) = O(n) because the work-per-level forms a geometric series. For a worst-case O(n) guarantee, Hoare’s algorithm can be combined with the Median of Medians pivot-selection routine (Blum, Floyd, Pratt, Rivest, Tarjan 1973), yielding the BFPRT algorithm; in practice the constant factor of median-of-medians is large enough that randomized quickselect is preferred whenever the worst case is acceptable. Quickselect is the canonical answer to the “k-th largest element” interview problem (LeetCode 215) and underlies the production C++ std::nth_element, which uses introselect — the introspective hybrid that falls back to median-of-medians when randomized pivots fail (Musser 1997).

1. Intuition — Asking “Which Side Is My Element On?”

Imagine you have a basket of 100 unsorted apples and you want the apple that would be ranked 23rd by weight (i.e., 22 lighter apples and 77 heavier apples surround it in the sorted order). The naïve approach is to sort all 100 apples by weight — O(n log n) — and pick index 22 (zero-indexed) of the sorted array. But sorting computes far more information than you need: it also tells you the rankings of all the other 99 apples, which you do not care about.

Quickselect’s insight is that you can use Quicksort’s partition primitive — pick a pivot apple, separate the remaining apples into “lighter than pivot” and “heavier than pivot” piles, and place the pivot at the boundary — and then only recurse on the side that contains rank 23. After one partition step, you know exactly which pile your target belongs to (because partitioning has placed the pivot at its final sorted position, so its rank is known). You discard the entire other pile without inspecting any of its elements. Each subsequent partition halves (in expectation) the size of the surviving subproblem.

This is the key qualitative difference from quicksort: quicksort recurses on both sides of the partition; quickselect recurses on only one. The work-per-level for quicksort is Θ(n) regardless of recursion depth (because the total subarray sizes at each level sum to n), giving T(n) = 2T(n/2) + O(n) = O(n log n). The work-per-level for quickselect halves at each level (because we discard one side), giving T(n) = T(n/2) + O(n) = O(n) — a much faster geometric collapse to linear time.

The intuition for why the geometric collapse gives O(n): the first partition does n work, the second does n / 2 work, the third does n / 4, and so on. The total is n + n/2 + n/4 + … = n · (1 + 1/2 + 1/4 + …) = 2n, which is O(n). This is the same kind of argument that makes amortized analysis of dynamic-array doubling work.

2. Tiny Worked Example (n = 7, find k = 3)

Find the 3rd-smallest (zero-indexed: index 3, i.e., the 4th order statistic — the median of [1, 2, 3, 4, 5, 6, 7]) in [5, 2, 8, 1, 9, 3, 7].

Use Lomuto partition with the last element as pivot.

Iteration 1: array = `[5, 2, 8, 1, 9, 3, 7]`, lo=0, hi=6, target k=3

Pivot = arr[6] = 7. Partition:

Walk j from 0 to 5; maintain i = -1 (boundary of "≤ pivot" region).
j=0, arr[0]=5 ≤ 7: i=0, swap arr[0]↔arr[0] (no-op). Array: [5, 2, 8, 1, 9, 3, 7]
j=1, arr[1]=2 ≤ 7: i=1, swap arr[1]↔arr[1] (no-op). Array: [5, 2, 8, 1, 9, 3, 7]
j=2, arr[2]=8 > 7: skip.                           Array: [5, 2, 8, 1, 9, 3, 7]
j=3, arr[3]=1 ≤ 7: i=2, swap arr[2]↔arr[3].       Array: [5, 2, 1, 8, 9, 3, 7]
j=4, arr[4]=9 > 7: skip.                           Array: [5, 2, 1, 8, 9, 3, 7]
j=5, arr[5]=3 ≤ 7: i=3, swap arr[3]↔arr[5].       Array: [5, 2, 1, 3, 9, 8, 7]

After scan: swap arr[i+1]↔arr[hi] to place pivot:
swap arr[4]↔arr[6].                                Array: [5, 2, 1, 3, 7, 8, 9]
                                                              ↑
                                                          pivot at index 4

Pivot’s final position: p = 4. We want index k = 3. Since p > k, the target is in the left subarray arr[0..3]. Discard arr[4..6].

Iteration 2: array = `[5, 2, 1, 3, 7, 8, 9]`, lo=0, hi=3, target k=3

Pivot = arr[3] = 3. Partition:

i = -1.
j=0, arr[0]=5 > 3: skip.                           Array: [5, 2, 1, 3, 7, 8, 9]
j=1, arr[1]=2 ≤ 3: i=0, swap arr[0]↔arr[1].       Array: [2, 5, 1, 3, 7, 8, 9]
j=2, arr[2]=1 ≤ 3: i=1, swap arr[1]↔arr[2].       Array: [2, 1, 5, 3, 7, 8, 9]

After scan: swap arr[i+1]↔arr[hi] to place pivot:
swap arr[2]↔arr[3].                                Array: [2, 1, 3, 5, 7, 8, 9]
                                                              ↑
                                                        pivot at index 2

Pivot’s final position: p = 2. We want k = 3. Since p < k, the target is in the right subarray arr[3..3] (only one element).

Iteration 3: array = `[2, 1, 3, 5, 7, 8, 9]`, lo=3, hi=3

Single-element subarray; the pivot is arr[3] = 5, partition trivially returns p = 3 = k.

Answer: arr[3] = 5.

Verifying against the sorted version [1, 2, 3, 5, 7, 8, 9]: index 3 is indeed 5. ✓

Notice that we never sorted the right half [7, 8, 9] of iteration 1, nor the left half [2, 1] of iteration 2. Quickselect computed the answer using only the partition steps strictly necessary to localize index k — a small fraction of the work a full quicksort would have done.

3. Pseudocode — Lomuto Variant

quickselect(arr, k):
    """Returns the k-th smallest element (0-indexed) of arr."""
    lo := 0
    hi := length(arr) - 1
    while lo < hi:
        pivot_idx := random_int(lo, hi)            # randomized pivot
        swap arr[pivot_idx], arr[hi]               # move pivot to end
        p := lomuto_partition(arr, lo, hi)
        if p == k:
            return arr[k]
        elif p < k:
            lo := p + 1                            # target is in right half
        else:
            hi := p - 1                            # target is in left half
    return arr[lo]                                 # lo == hi at this point

lomuto_partition(arr, lo, hi):
    pivot := arr[hi]
    i := lo - 1
    for j := lo to hi - 1:
        if arr[j] <= pivot:
            i := i + 1
            swap arr[i], arr[j]
    swap arr[i + 1], arr[hi]
    return i + 1

The iterative form (with while lo < hi) replaces the natural recursion with a loop, which is sometimes preferred to avoid stack-depth concerns. The recursive form is identical in structure: after partitioning, recurse on either quickselect(arr, lo, p − 1, k) or quickselect(arr, p + 1, hi, k), never both.

4. Pseudocode — Hoare Variant

Hoare’s original FIND used his two-pointer partition, which is faster (~3× fewer swaps on average) but trickier:

quickselect_hoare(arr, lo, hi, k):
    while lo < hi:
        pivot_idx := random_int(lo, hi)
        swap arr[pivot_idx], arr[lo]
        p := hoare_partition(arr, lo, hi)          # returns split point, NOT pivot index
        if k <= p:
            hi := p
        else:
            lo := p + 1
    return arr[lo]

hoare_partition(arr, lo, hi):
    pivot := arr[lo]
    i := lo - 1
    j := hi + 1
    loop:
        repeat: i := i + 1
        until arr[i] >= pivot
        repeat: j := j - 1
        until arr[j] <= pivot
        if i >= j:
            return j
        swap arr[i], arr[j]

Subtle but important

Hoare partition’s return value is a split point such that everything in arr[lo..p] ≤ everything in arr[p+1..hi], but it is not the pivot’s final index. The pivot may end up anywhere on the left side. The recursion conditions accordingly use k <= p (not k == p followed by side selection), and the “found it” base case is reached when lo == hi. Mixing Hoare and Lomuto recursion conditions is one of the most common sources of off-by-one bugs in quickselect implementations.

5. Python Implementation

import random
 
def quickselect(arr: list[int], k: int) -> int:
    """Return the k-th smallest element (0-indexed) of arr.
    Uses randomized pivot Lomuto partition. Modifies arr in place.
    Expected O(n), worst-case O(n²)."""
    if not 0 <= k < len(arr):
        raise IndexError(f"k={k} out of range for arr of length {len(arr)}")
    return _quickselect(arr, 0, len(arr) - 1, k)
 
def _quickselect(arr, lo, hi, k):
    while lo < hi:
        pivot_idx = random.randint(lo, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]   # randomize pivot
        p = _partition(arr, lo, hi)
        if p == k:
            return arr[k]
        elif p < k:
            lo = p + 1
        else:
            hi = p - 1
    return arr[lo]
 
def _partition(arr, lo, hi):
    """Lomuto partition with arr[hi] as pivot; returns final pivot index."""
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

A few production-relevant notes. First, the randomized pivot (random.randint(lo, hi)) is essential: with a deterministic pivot like “always the last element,” adversarial inputs (sorted, reverse-sorted, killer sequences) will trigger the O(n²) worst case. Randomization makes adversarial input impossible without knowledge of the random seed. Second, the function modifies arr in place — quickselect is fundamentally an in-place algorithm. If you need to preserve the original, copy first. Third, the iterative loop avoids recursion-depth concerns; in Python a recursive version on a 1-million-element array could exceed the default recursion limit on a bad pivot sequence.

For the LeetCode 215 framing (“k-th largest”), translate k_largest = n - k:

def find_kth_largest(arr: list[int], k: int) -> int:
    return quickselect(arr, len(arr) - k)

6. Complexity Analysis

6.1 Expected Time — The `O(n)` Derivation

The crux is the recurrence for expected work. Assume each pivot is chosen uniformly at random from [lo, hi]. After partitioning a subarray of size m, the pivot’s final position is uniformly distributed over the m possible ranks, so the surviving subarray (the side containing target index k) has size uniformly distributed over 0, 1, …, m − 1. The expected size of the surviving subarray is therefore (m − 1) / 2 ≈ m / 2.

The recurrence for expected time T(n) is then:

T(n) = T(expected subarray size) + O(n)
     ≈ T(n / 2) + O(n)

where:

T(n) is the expected number of operations to find the k-th element in a subarray of size n.
The O(n) term is the cost of one partition step on a size-n subarray.
The T(n / 2) term reflects that, in expectation, half the subarray is discarded each iteration.

Solving by repeated substitution:

T(n) ≤ c · n + T(n / 2)
     ≤ c · n + c · (n / 2) + T(n / 4)
     ≤ c · n + c · (n / 2) + c · (n / 4) + … + T(1)
     = c · n · (1 + 1/2 + 1/4 + …)
     ≤ c · n · 2
     = O(n)

where:

c is the constant hidden in the O(n) partition cost.
The geometric series 1 + 1/2 + 1/4 + … = 2 converges (this is the standard infinite-geometric-sum identity for ratio 1/2).

So the expected total work is at most 2cn = O(n). The key insight is the geometric-series collapse: because the surviving subproblem halves at each step (in expectation), the total work is dominated by the first few partition steps, and the tail contributes only a constant factor.

CLRS §9.2 (Theorem 9.2 in the 3rd edition) proves the expected running time of randomized-select is Θ(n) via an indicator-variable argument that bounds the expected total subarray sizes; a careful accounting yields an expected-comparison bound on the order of 4n (uniform over the choice of k). For the median specifically (k = n/2, the worst k), the expected comparison count is tighter — about n(2 + 2ln2) ≈ 3.39n, and smaller for k near the ends (Quickselect, Wikipedia). Either way the leading term is linear; the geometric collapse above is the intuition, and the indicator-variable bound is the rigorous version.

6.2 Worst Case — `O(n²)`

If pivots are chosen adversarially (or, with a fixed-pivot-rule like “always last element,” if the input is sorted), partitioning produces splits of (m − 1, 0) — completely unbalanced. The surviving subproblem shrinks by 1 each step, not halving. Total work: n + (n − 1) + (n − 2) + … + 1 = n(n + 1)/2 = Θ(n²).

With uniformly random pivot selection, the probability of hitting the worst case is (1 / n!) — astronomically small for any meaningful n. Worst-case input for randomized quickselect requires the adversary to know the random seed, which is generally not the threat model.

For a deterministic worst-case O(n) guarantee, see Median of Medians (the BFPRT algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan 1973): it picks the pivot such that the pivot’s rank is guaranteed between the 30th and 70th percentile of the subarray, ensuring at least 30% of elements are discarded each iteration (per Median of medians, Wikipedia). The full recurrence has two recursive terms — one to find the median-of-medians pivot itself and one for the surviving selection call:

T(n) ≤ T(n / 5) + T(7n / 10) + c · n

where T(n/5) is the cost of recursively selecting the median of the ⌈n/5⌉ group-medians, T(7n/10) bounds the surviving subproblem after discarding ≥30%, and c·n is the partition + grouping work. Because 1/5 + 7/10 = 9/10 < 1, the recursion fractions sum to less than one and the recurrence solves to T(n) = O(n) worst-case (substitution: T(n) ≤ c'·(9n/10) + cn ≤ c'n once c' ≥ 10c).

The constant factor is what kills it in practice. Median-of-medians performs on the order of ~18–22n comparisons (the standard groups-of-5 variant), against randomized quickselect’s ~3.4n for the median — roughly a 5–6× gap in comparisons, and larger still once the extra element movement and recursion overhead are counted (danlark.org, Miniselect, 2020). So BFPRT is rarely the right choice unless adversarial input is a real threat; the Floyd–Rivest algorithm (~3n/2 comparisons for the median, discussed in §7) is the constant-factor champion when only the average case matters.

6.3 Space

Auxiliary space is O(1) for the iterative version (just a few index variables and the swap temp). The recursive version uses O(log n) expected stack depth, O(n) worst case — but with tail-call elimination on the larger sub-problem, the recursive version’s stack depth can be bounded at O(log n) worst-case.

7. Comparison with Heap-Based Top-K

A common alternative for “find the k-th largest element” or “find the top-k elements” is to maintain a Binary Heap of size k while streaming through the array:

Approach	Time	Space	Modifies input?	Returns
Quickselect	`O(n)` expected, `O(n²)` worst	`O(1)` aux + in-place modification	Yes	The single k-th element
Min-heap of size k	`O(n log k)`	`O(k)`	No	Top-k elements (the heap contents)
Full sort + index	`O(n log n)`	`O(n)` if not in-place	Depends	Any rank

The trade-offs:

Quickselect wins on the asymptotic time bound (O(n) vs O(n log k)), and dramatically so when k is close to n / 2. But if you need only the top-k elements (not just the k-th boundary), quickselect must be augmented with a partial-sort pass on the surviving partition. Practical implementations often combine quickselect (to localize the k-th element) with a simple scan to extract the top-k.
Heap wins when the input is streaming (cannot be modified in place, cannot be fully materialized) — quickselect requires random access to the entire array. For a true stream, the size-k min-heap is the canonical approach.
Heap wins on worst-case bound — O(n log k) is deterministic, while quickselect’s O(n) is only expected. If the adversary can craft inputs and the random seed is known (rare in practice), heap is more robust.
Heap wins on small k — for k = 10 on n = 10⁹, n log k ≈ n · 3.3 ≈ 3.3 · 10⁹ operations vs quickselect’s ~2n = 2 · 10⁹; the heap constant factor is also smaller per operation. The cross-over depends on hardware and k / n ratio.

The interview-friendly summary: for in-memory single-shot top-k, prefer quickselect; for streaming or small k with worst-case guarantees, prefer the heap.

There is also the Floyd–Rivest algorithm (CACM 1975), which improves the constant factor of randomized quickselect by sampling a small subset to choose better pivots, achieving n + min(k, n − k) + O(√(n log n)) comparisons in expectation — close to the information-theoretic lower bound. It is rarely implemented because the constant-factor savings rarely justify the implementation complexity.

8. Variants and Production Use

8.1 Introselect

Musser’s 1997 paper introduced introselect, the selection counterpart to Intro Sort (Musser 1997). It runs quickselect (Musser’s variant uses a median-of-3 pivot rather than a randomized one), monitoring the rate of subproblem shrinkage: a depth counter is decremented each time the surviving subproblem fails to shrink by enough; when the counter hits zero — i.e. quickselect is making poor progress — the algorithm switches pivot strategy for the remainder to recover O(n) worst-case time. Musser’s original proposal falls back to Median of Medians; in practice, library implementations choose cheaper fallbacks (see §8.3). C++‘s std::nth_element is required by the C++ standard only to have O(n) average time; the standard says nothing about the worst case, which is why real implementations differ in whether they bound it at all.

8.2 Multiple Selection

To find several order statistics simultaneously (e.g., the 25th, 50th, and 75th percentiles), naïve approaches run quickselect once per query for O(qn) expected time on q queries. Better algorithms partition the work across queries: process all queries in one descent of the partition tree, recursing on a partition side only if at least one query falls in it. The Floyd–Rivest variant supports this naturally.

8.3 Approximate / Streaming Selection

For data streams where n is unknown or unbounded, neither quickselect nor heaps are directly applicable. Sketches like the Greenwald–Khanna algorithm (2001) or the t-digest (Dunning 2014) provide approximate quantile estimates with bounded error in O(log² n) or O(1) amortized space per quantile. These are not “quickselect” but solve the analogous selection problem in a different cost model.

8.4 What the standard libraries actually do

It is a common myth that every std::nth_element is a clean introselect with an O(n) worst case. The two major C++ standard libraries diverge sharply, and one of them is quadratic:

libstdc++ (GCC) implements introselect, but its fallback is heapselect, not median-of-medians: it runs at most 2·log₂(n) quickselect partition steps, and if it has not localized the target by then, it builds a heap over the remaining subrange and extracts. The worst case is therefore O(n log n), not the textbook O(n) — Musser’s median-of-medians fallback was deliberately swapped for the simpler, faster-in-practice heapselect (danlark.org, Miniselect, 2020).
libc++ (LLVM/Clang) uses median-of-3 quickselect with no fallback at all. This is genuinely quadratic on adversarial input — a “median-of-3 killer” sequence drives it to Θ(n²). This conforms to the C++ standard (which constrains only the average case) but is a real, reported defect: LLVM issue #52747 (“libc++ std::nth_element is quadratic, should be linear”) was open and confirmed as of mid-2025, with the reporter demonstrating comparison counts scaling from ~2,700 at n=100 to ~10.2 million at n=6,400.

The takeaway for interviews and production: do not assume std::nth_element gives a hard O(n) guarantee. If you need a guaranteed linear worst case, you must implement Median of Medians yourself or use a library (e.g. miniselect) that offers it explicitly.

Uncertain

Verify: the current state of LLVM issue #52747 and whether libc++‘s std::nth_element has since been changed to add a worst-case fallback. Reason: confirmed open/quadratic as of mid-2025 per the issue thread fetched here, but this is fast-moving implementation detail that may change in a later libc++ release. To resolve: re-check the issue status and the libc++ <__algorithm/nth_element.h> source on the relevant release branch. uncertain

9. Stability and Adaptiveness

Stable: No in the sense that quickselect’s partition step swaps elements freely, so equal-valued elements may be reordered. However, “stability” in the context of selection (as opposed to sorting) is rarely a concern — the algorithm returns a single element, not a relative ordering.

Adaptive: No. Quickselect on already-sorted input is not faster — and with a bad pivot rule (always-last) it is actually O(n²) worse. The algorithm makes no use of pre-existing order in the input.

10. Pitfalls

Off-by-one between Hoare and Lomuto recursion conditions. Lomuto’s partition returns the pivot’s final index; Hoare’s returns a split point. The recursion conditions differ accordingly. Mixing them causes infinite loops or wrong answers.
Forgetting the random pivot. Deterministic last-element pivot on sorted input degenerates to O(n²). In production code, randomization is essential. In interview code, mention the randomization step explicitly even if your example uses a deterministic pivot for clarity.
k-th smallest vs k-th largest confusion. LeetCode 215 asks for the k-th largest; the natural quickselect formulation finds the k-th smallest. The translation k_largest = n - k (zero-indexed: k_largest_idx = n - k_one_indexed) is easy to get wrong. Be explicit about indexing conventions.
Recursion-depth overflow on bad inputs. A recursive quickselect on a 1-million-element array can blow the stack on adversarial input. Use the iterative form, or use tail-call elimination on the larger subproblem.
Mutating shared state. Quickselect modifies the input array in place. If the caller still needs the original array, copy first. Failing to do so is a frequent silent bug.
Returning the index instead of the value (or vice versa). The interview question may want either; clarify before writing code. The standard std::nth_element reorders the array such that arr[n] is the desired element and partial ordering holds around it — the algorithm returns nothing, just rearranges.
Assuming the algorithm sorts the array. It does not. Quickselect leaves the array in a partial-sort state where arr[k] is correct, everything < arr[k] is in arr[0..k − 1] (in arbitrary order), and everything > arr[k] is in arr[k + 1..n − 1] (in arbitrary order). If the caller expects a fully sorted array, this is a correctness bug.

11. Diagram

flowchart TD
  Start["quickselect(arr, k)<br/>n elements, want k-th smallest"]
  Start --> Pick["Pick random pivot from [lo, hi]"]
  Pick --> Part["Partition: arr → < pivot | pivot | > pivot<br/>O(n) work"]
  Part --> Decide{"Pivot at index p"}
  Decide -- "p == k" --> Done["Return arr[k]"]
  Decide -- "p < k" --> Right["Discard left half<br/>Recurse on arr[p+1..hi]<br/>(target is to the right)"]
  Decide -- "p > k" --> Left["Discard right half<br/>Recurse on arr[lo..p-1]<br/>(target is to the left)"]
  Right --> Pick
  Left --> Pick

What this diagram shows. The control flow of quickselect’s main loop, showing the central design choice that distinguishes it from full quicksort. After each partition step, the algorithm inspects the pivot’s resulting index p and the target index k and discards one entire side of the partition — the side that does not contain k. This single-side recursion is the source of the O(n) expected time bound: each iteration shrinks the surviving subproblem by half (in expectation), and the work per iteration also halves, producing the geometric series n + n/2 + n/4 + … = 2n total work. Compare to Quicksort’s diagram, which would show recursion arrows on both sides of every partition — the missing recursion arrow is exactly the algorithmic insight that makes quickselect linear-time. The base case is p == k (we have placed the target element at its final sorted index).

12. Common Interview Problems

Problem	Source	Quickselect application
Kth Largest Element in an Array	LeetCode 215	The canonical quickselect problem; `k_largest = n - k` translation
Top K Frequent Elements	LeetCode 347	Quickselect on (element, frequency) pairs; alternative to heap solution
K Closest Points to Origin	LeetCode 973	Quickselect on Euclidean distances
Wiggle Sort II	LeetCode 324	Find median via quickselect, then interleave
Find Median from Data Stream	LeetCode 295	Streaming variant — quickselect is not the answer here; use two heaps. Interesting contrast problem
Sort Colors	LeetCode 75	Not quickselect per se; uses Dutch National Flag partition, conceptually related
Reservoir Sampling	Folklore	Conceptually adjacent — both use random sampling for selection problems

LeetCode 215 is the problem to know cold. The expected interview flow: the candidate first proposes the heap solution (O(n log k)), then the interviewer asks “can you do better?”, and quickselect (O(n) expected) is the upgrade. Bonus points for mentioning the worst-case O(n²) and the Median of Medians guarantee.

13. Open Questions

What is the exact constant factor for the expected number of comparisons in randomized quickselect for k = n/2 (median)? CLRS gives ≤ 4n; tighter bounds exist in the literature — verify the current best.
On modern superscalar CPUs with branch prediction, does the data-dependent branching of the partition step cause significant pipeline stalls relative to predictable algorithms (heap-based)? Empirical numbers vary across architectures.
How does quickselect interact with cache locality on large arrays? The first partition pass is cache-friendly (sequential access), but subsequent passes operate on smaller and smaller subarrays that fit progressively better in L1 — the practical performance is often better than the asymptotic bound suggests.

14. See Also

Quicksort — the parent algorithm; quickselect is its single-side recursive variant
Median of Medians — deterministic worst-case O(n) selection (the BFPRT algorithm)
Intro Sort — Musser’s introspective sorting algorithm; introselect is its selection sibling
Heap Sort — alternative for top-k via Binary Heap
Binary Heap — backbone of the heap-based top-k approach
Top K Elements — interview-pattern note covering both quickselect and heap approaches
Dutch National Flag — three-way partition variant useful for selection on arrays with many duplicates
Big-O Notation
SWE Interview Preparation MOC

vault

Explorer

Quickselect

Quickselect

1. Intuition — Asking “Which Side Is My Element On?”

2. Tiny Worked Example (n = 7, find k = 3)

Iteration 1: array = `[5, 2, 8, 1, 9, 3, 7]`, lo=0, hi=6, target k=3

Iteration 2: array = `[5, 2, 1, 3, 7, 8, 9]`, lo=0, hi=3, target k=3

Iteration 3: array = `[2, 1, 3, 5, 7, 8, 9]`, lo=3, hi=3

3. Pseudocode — Lomuto Variant

4. Pseudocode — Hoare Variant

5. Python Implementation

6. Complexity Analysis

6.1 Expected Time — The `O(n)` Derivation

6.2 Worst Case — `O(n²)`

6.3 Space

7. Comparison with Heap-Based Top-K

8. Variants and Production Use

8.1 Introselect

8.2 Multiple Selection

8.3 Approximate / Streaming Selection

8.4 What the standard libraries actually do

9. Stability and Adaptiveness

10. Pitfalls

11. Diagram

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Quickselect

Quickselect

1. Intuition — Asking “Which Side Is My Element On?”

2. Tiny Worked Example (n = 7, find k = 3)

Iteration 1: array = [5, 2, 8, 1, 9, 3, 7], lo=0, hi=6, target k=3

Iteration 2: array = [5, 2, 1, 3, 7, 8, 9], lo=0, hi=3, target k=3

Iteration 3: array = [2, 1, 3, 5, 7, 8, 9], lo=3, hi=3

3. Pseudocode — Lomuto Variant

4. Pseudocode — Hoare Variant

5. Python Implementation

6. Complexity Analysis

6.1 Expected Time — The O(n) Derivation

6.2 Worst Case — O(n²)

6.3 Space

7. Comparison with Heap-Based Top-K

8. Variants and Production Use

8.1 Introselect

8.2 Multiple Selection

8.3 Approximate / Streaming Selection

8.4 What the standard libraries actually do

9. Stability and Adaptiveness

10. Pitfalls

11. Diagram

12. Common Interview Problems

13. Open Questions

14. See Also

Graph View

Table of Contents

Backlinks

Iteration 1: array = `[5, 2, 8, 1, 9, 3, 7]`, lo=0, hi=6, target k=3

Iteration 2: array = `[5, 2, 1, 3, 7, 8, 9]`, lo=0, hi=3, target k=3

Iteration 3: array = `[2, 1, 3, 5, 7, 8, 9]`, lo=3, hi=3

6.1 Expected Time — The `O(n)` Derivation

6.2 Worst Case — `O(n²)`