cf.completefrontend
SORTING · CORE

Quickselect

Find the k-th smallest item without sorting everything, by partitioning around a pivot and keeping only the side that holds position k.

Time O(n) on averageSpace O(1)4 practice problemsStep-through picture

The idea

Sometimes you don't need the whole list sorted. You only need one position of the sorted order: the median, the 3rd largest, the 95th percentile. Sorting first costs O(n log n). Quickselect does it in O(n) on average.

It uses quick sort's partition step. After partitioning around a pivot, the pivot sits at its final sorted index, store. If store is exactly k, that is the answer. If store is less than k, the answer is to the right; otherwise it is to the left. Unlike quick sort, quickselect only continues on one side.

Each round throws away the side that can't hold the answer. On average that is about half the list, so the work is n + n/2 + n/4 + ..., which adds up to about 2n.

An everyday example

Finding the 5th tallest without lining everyone up

A coach needs the 5th shortest player, not a full lineup. She picks one player and splits the group: shorter ones on the left, the rest on the right. If exactly four players are on the left, the chosen player is the 5th shortest: done. If six are on the left, the answer is among them, and the right group can go home. She repeats with the group that is left.

How the example maps to the code
In the exampleIn the code
The chosen playerpivot = items[high]
How many are shorterstore, the pivot's final index
Exactly four shorter: foundif (store === k) return items[k]
Sending one group homelow = store + 1 or high = store - 1

From the slow way to quickselect

  1. Suppose you need the median of a list, or its 3rd smallest item. The obvious way is to sort the whole list and read index k. That costs O(n log n) and produces far more than you asked for: the full order of every item, when you wanted one position.
  2. Quick sort's partition step already finds one position exactly. After partitioning around a pivot, the pivot sits at index store, its final sorted place, with every smaller item to its left and the rest to its right. If store happens to equal k, the pivot is the answer and we're done.
  3. If store is not k, the partition still tells us which side the answer is on. When store < k, the answer is among the items to the right, so the left side and the pivot can be thrown away. When store > k, it is on the left. Quick sort would now sort both sides; we only need one.
  4. So keep a range low..high that must contain index k. Partition it, compare store with k, and shrink the range to the side that holds k. On average each round keeps about half, so the work is about n + n/2 + n/4 + ..., less than 2n partition steps. Partition, then keep only the side with k: that loop is quickselect.

How it works

  1. Set low = 0 and high = items.length - 1. The answer's index k (0-based) is inside this range.
  2. Partition items[low..high] around pivot = items[high], exactly as quick sort does. The pivot ends at store.
  3. If store === k, return items[k].
  4. If store < k, the answer is to the right of the pivot: low = store + 1.
  5. Otherwise it is to the left: high = store - 1.
  6. When the range is a single item, that item is the answer.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function quickselect(items, k) {
  2. let low = 0;
  3. let high = items.length - 1;
  4. while (low < high) {
  5. const pivot = items[high];
  6. let store = low;
  7. for (let j = low; j < high; j++) {
  8. if (items[j] < pivot) {
  9. [items[store], items[j]] = [items[j], items[store]];
  10. store++;
  11. }
  12. }
  13. [items[store], items[high]] = [items[high], items[store]];
  14. if (store === k) return items[k];
  15. if (store < k) low = store + 1;
  16. else high = store - 1;
  17. }
  18. return items[k];
  19. }

How fast it is

TimeO(n) on average
Extra memoryO(1)

Each partition is linear in the range, and the range shrinks by about half each round on average, so the total is about 2n. It works in place with a loop, not recursion.

  • Best caseO(n)

    The first pivot lands exactly at k, like k = 2 in [2, 9, 1, 7, 5]: pivot 5 has two smaller items, lands at index 2, and is returned after one partition of 4 comparisons.

  • Average caseO(n)

    Random data or random pivots. Each round keeps about half on average. Finding the median of 10,000 random numbers took about 33,000 comparisons, about 3.3n.

  • Worst caseO(n²)

    Each pivot is the biggest or smallest in its range: with the last item as pivot, an already sorted list and k = 0. On 1,000 sorted items that is 999 rounds and 499,500 comparisons.

Common mistakes

  • Mixing up 1-based and 0-based k. "The 3rd smallest" is index 2.
  • For the k-th largest, searching for index k - 1 instead of n - k.
  • Forgetting that it rearranges the input array. Copy it first if the caller still needs the original order.
  • Using the last item as the pivot on sorted input, which makes it O(n²). Swap a random item into high first.

When to use it

Look for these clues in a problem:

  • The question asks for the k-th smallest or k-th largest item, a median, or a percentile.
  • You need the k smallest items in any order, not sorted.
  • Sorting would work but the problem hints at better than O(n log n).

Check yourself

Answer each one in your head first, then open it.

Why does quickselect average O(n) when quick sort averages O(n log n)?

Quick sort partitions both sides at every level, so each level costs O(n). Quickselect keeps only one side, so the costs shrink, n + n/2 + n/4 + ..., and add up to less than 2n.

What index do you pass for the 2nd largest of 7 items?

Index 5, which is n - k = 7 - 2. Sorted ascending, the largest is at 6 and the 2nd largest at 5.

After finding the median, which items are guaranteed to be to its left?

Every item smaller than the median, possibly with some equal ones. They are in no particular order, because quickselect never sorts the sides.

Why does the loop condition use low < high instead of low <= high?

When low === high, the range has one item, and the promise says it is the answer. Partitioning a one-item range would do nothing useful, so the loop stops and returns items[k].

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one promise: the item that belongs at sorted index k is somewhere in items[low..high], and every item before low is smaller than or equal to every item in the range, while every item after high is bigger than or equal to them. At the start the range is the whole list, so the promise holds.

Partitioning low..high puts the pivot at store, with exactly the smaller items of the range before it. Together with the items before low, that means exactly store items of the whole list belong before the pivot, so the pivot's sorted index is store. If store === k, it is the answer. If store < k, the answer is bigger than the pivot and everything left of it, so it is in store + 1..high. If store > k, it is in low..store - 1. Either way the promise still holds for the new range.

Each round leaves out at least the pivot, so the range shrinks by at least one and the loop ends. It ends either by finding store === k, or with low === high, a one-item range. By the promise, that single item is the answer, so returning items[k] is correct.

Going deeper

3 more ideas

Why throwing away a side is safe

After partitioning, every item before store is smaller than the pivot and every item after it is not. So the items before store are exactly the store smallest items (in some order), and the pivot is the next one. If k > store, the k-th smallest is not among the left items or the pivot, so only the right side matters. The same reasoning works the other way.

Average and worst case

With good pivots each round keeps about half, so the total is about n + n/2 + n/4 + ... = 2n: O(n). With the worst pivots (always the smallest or largest), each round removes only one item: O(n²). A random pivot makes the bad case extremely unlikely. There is also a guaranteed O(n) method (median of medians), but it is slower in practice.

k-th largest and the order of the rest

The k-th largest (1-based) is the item at sorted index n - k. After quickselect, the items before index k are the k smallest, but they are not sorted among themselves. If you need them sorted, sort just those k items afterwards.

Work it by hand

Every step in a table, with why

Find index k = 2, the 3rd smallest of 8 numbers. The range shrinks from both ends until it is a single index.

items = [15, 4, 22, 9, 30, 11, 6, 18], k = 2

SteplowhighpivotstoreitemsWhat happensWhy
107185[15, 4, 9, 11, 6, 18, 30, 22]5 > 2: high = 4Five items are smaller than 18, so it lands at index 5. The answer must be in 0..4; 30 and 22 are gone for good.
20461[4, 6, 9, 11, 15, 18, 30, 22]1 < 2: low = 2Only 4 is smaller than 6. The answer is to the right of index 1, so low moves up.
324154[4, 6, 9, 11, 15, 18, 30, 22]4 > 2: high = 39 and 11 are smaller than 15, so it stays at index 4. Drop it.
423113[4, 6, 9, 11, 15, 18, 30, 22]3 > 2: high = 29 is smaller than 11, so 11 stays at index 3. The range shrinks to 2..2.
522--[4, 6, 9, 11, 15, 18, 30, 22]low < high is false: return items[2]One index is left, and the promise says it holds the answer. The last line returns items[k].

It returns 9 after 4 partitions and 14 comparisons. Sorted, the list is [4, 6, 9, 11, 15, 18, 22, 30], and index 2 is indeed 9. Note that 30 and 22 were never put in order.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
QuickselectO(n)O(1)You need one order position, like a median or percentile, from an array you may rearrange. Linear on average.
Sort, then indexO(n log n)O(n)You will ask for many positions from the same data, or the list is small and simple code matters most.
Heap of size kO(n log k)O(k)Data arrives as a stream, can't be rearranged, or k is small compared to n.
Counting sortO(n + k)O(k)Values are small whole numbers, like scores from 0 to 100: count them and walk the counts to position k.

Extra memory: O(1): a loop with low, high, store, and pivot, working inside the array. A recursive version would use stack space instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Quickselect and the other approaches, on a scale where each line up is 10 times more steps.
  • Quickselect O(n)
  • Sort, then index, Heap of size k O(n log n)
  • Counting sort O(n + k)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Quickselect101,0001 million
Sort, then index339,96620 million
Heap of size k339,96620 million
Counting sort202,0002 million

Inputs that need care

5 tricky inputs
One item: [42] with k = 0
low < high is 0 < 0, false, so the loop never runs and it returns items[0], which is 42.
k outside the list: k = 3 for 3 items, or k = -1
The promise is false from the start, and the code returns undefined. Check 0 <= k < items.length before calling.
All equal: 1,000 copies of 7, looking for the median
items[j] < pivot is never true, so each round removes only the pivot: 501 rounds and about 375,000 comparisons. A three-way partition that groups equal items would answer in one round.
Already sorted input with the last item as pivot
Each pivot is the biggest in its range, so the range shrinks by one per round: O(n²). Swapping a random item into high before each partition makes this extremely unlikely.
The caller still needs the original order
Quickselect rearranges items in place. Pass a copy, quickselect([...items], k), if the order matters elsewhere.

Variations and follow-ups

Twists interviewers add

The k smallest items

After quickselect returns, items[0..k-1] holds the k smallest items (in no particular order) and items[k] is the next one. So top-k lists, like the 10 cheapest products, take O(n) on average, plus O(k log k) if you want them sorted.

Random pivot

Swap a random item of low..high into high before partitioning. Then no fixed input is slow, and the expected number of comparisons is linear for every input.

Median of medians

Split the range into groups of 5, take each group's median, and use the median of those as the pivot. It guarantees a pivot that throws away at least about 30% each round, so the worst case is O(n). It is slower in practice, so it is mostly used as a fallback, as in introselect.

Heap of size k

Keep the k smallest items seen so far in a max-heap of size k, replacing its top when a smaller item arrives. It costs O(n log k) but works on a stream where you can't hold or rearrange the whole list.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "k-th largest", "k-th smallest", "median", "top k", or "closest k points" when the answer doesn't need to be sorted. Sorting works, but the follow-up will ask for better than O(n log n).
  • State the conversion first: the k-th largest (1-based) is at sorted index n - k, and the k-th smallest is at k - 1. Off-by-one errors here are the most common bug.
  • Explain it as "quick sort that only recurses into one side", and give the halving sum n + n/2 + n/4 + ... < 2n for the average case.
  • The usual follow-up is "what's the worst case, and how do you avoid it?". Answer: O(n²) with consistently bad pivots; a random pivot makes it expected O(n), and median of medians guarantees O(n).

Where frontend code uses it

The same idea in real UI code
  • Performance dashboards show median and 95th percentile load times. Quickselect finds these without sorting thousands of samples.
  • Picking the k nearest items to a point, such as the closest map markers to the user, then sorting only those k for display.
  • Robust chart scaling: finding the 1st and 99th percentile values to ignore outliers when setting an axis range.

Related algorithms