Quickselect finds the kth-smallest element of an array in average O(n) time without fully sorting. It uses quicksort's partition step: pick a pivot, rearrange so smaller values are left and larger are right, which lands the pivot at its final sorted position p. If p equals k you're done; otherwise you recurse into only the side (left or right) that contains rank k, discarding the other half.

Why is quickselect average O(n) when quicksort is O(n log n)?

Quicksort recurses into both halves after each partition; quickselect recurses into only one. On average each partition roughly halves the search range, so the work is n + n/2 + n/4 + ... which sums to about 2n — linear. Quicksort must sort both sides, adding the extra log n factor.

What is quickselect's worst case?

O(n squared), when pivots are consistently poor (for example, always the smallest or largest element on an adversarial input), so each partition shrinks the range by only one. Randomizing the pivot makes this astronomically unlikely, and the median-of-medians pivot rule guarantees O(n) worst case at the cost of a larger constant.

Algorithms · Selection

Quickselect.

Q: What is quickselect used for?

Finding medians, percentiles, and top-k or bottom-k elements without a full sort. It underlies fast 'kth largest', 'median of a stream window', and selection routines in standard libraries (like C++'s nth_element). When you only need one order statistic, quickselect beats sorting.

You want the 5th-smallest value — or the median. Sorting the whole array gets it, but that’s O(n log n) of work for a single answer. Quickselect borrows quicksort’s partition and throws away half the array at every step: partition around a pivot, ask which side your target rank lives in, and recurse into only that one. Average linear time, no full sort.

Average O(n) · worst O(n²) · in-place · selection

rank k

The index the answer would sit at if the array were sorted (0-based).

partition

Rearrange around a pivot so smaller-left, larger-right; the pivot lands at its final spot.

pivot index p

Where the pivot ends up. Compare it to k to pick a side.

recurse one side

Discard the half that can’t contain rank k. This is the whole speedup.

quickselect.js — find rank k, keep one side

Ready

We’re hunting rank k = 4 — the 5th-smallest value. Each Step partitions the active range around a pivot (the last element), lands it at index p, then keeps only the side that contains k.

target k

0–8

active range

compares

How it works

Quickselect is quicksort that stops caring about the half it doesn’t need. After one partition, the pivot sits at its true sorted position p. That single fact tells you everything: if p == k the pivot is the answer; if k < p the answer is somewhere on the left; if k > p, on the right. Whichever side, you drop the other entirely.

Partition the active range

Pick a pivot (here the last element), sweep once moving smaller values left, and place the pivot at the boundary — its final index p.

Compare p to k

p == k → found it. k < p → recurse left. k > p → recurse right.

Discard the other half

Only one side can hold rank k, so the other is gone — the search range shrinks, usually by about half.

✓

Repeat until p == k

Each round works on a smaller range: n + n/2 + n/4 + … ≈ 2n. That’s why the average is linear.

Average

O(n)

Worst

O(n²)

Space

O(1) in-place

vs full sort

skips the log n

The code

# kth-smallest (0-indexed rank), average O(n) def quickselect(a, k): lo, hi = 0, len(a) - 1 while lo < hi: p = partition(a, lo, hi) # pivot lands at p if p == k: return a[p] elif p < k: lo = p + 1 # answer is on the right else: hi = p - 1 # answer is on the left return a[lo] def partition(a, lo, hi): pivot, i = a[hi], 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

Randomize the pivot (swap a random element to hi before partitioning) to make the O(n²) worst case astronomically unlikely. For a hard guarantee, the median-of-medians pivot rule gives worst-case O(n) — at a larger constant that usually isn’t worth it in practice.

Quick check

1. Why is quickselect average O(n) while quicksort is O(n log n)?

2. After a partition, the pivot index is p. When do you recurse right?

FAQ

What is quickselect used for?

Finding medians, percentiles, and top-k or bottom-k elements without fully sorting. It’s the engine behind fast "kth largest" and library selection routines like C++'s nth_element.

How do I find the median with it?

The median is just rank n/2 (for odd n). Run quickselect with k = n/2. For even n, take the two middle ranks and average them.

What’s the worst case, and how do I avoid it?

O(n²) on adversarial inputs with consistently bad pivots. Randomizing the pivot makes it practically impossible; median-of-medians guarantees O(n) worst case with a bigger constant.

Does it fully sort the array?

No — it only rearranges enough to place rank k correctly. The array ends up partially ordered around the pivots it chose, which is exactly the point: it does the minimum work for one answer.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Quickselect.

How it works

Partition the active range

Compare p to k

Discard the other half

Repeat until p == k

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Partition the active range

Compare p to k

Discard the other half

Repeat until p == k

The code

Quick check

FAQ

Keep going

Quicksort →

Heaps & Priority Queues →

Top-K Frequent →

Percentile Calculator →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.