Quickselect

Why this matters

Many programs need one value from a list, not the whole list in order. The median score of a class is one example. The tenth most expensive order is another. You can always sort the list and read the value at the right position. Sorting costs about n times log n steps, where n is the number of values and log n is roughly how many times you can halve n before it reaches 1. Quickselect finds the value in about n steps on average, so it is faster on large inputs and it is a common interview question.

Quickselect reuses the partition step from the quick sort lesson in this module. Quick sort partitions and then sorts both sides. Quickselect partitions and then searches only one side. That one change turns a sorting algorithm into a search algorithm.

This lesson covers finding one value. Sorting, merging and searching a sorted list are covered by the other lessons in this module.

Start with a plain problem

Suppose you have seven numbers:

7 2 9 4 1 8 6

Count positions from 0, as C++ does. Position 0 holds the first value. The k-th smallest value is the value that would sit at position k if the list were sorted. Position 0 is the smallest, position 1 is the second smallest, and so on.

If you sort the seven numbers, you get this:

1 2 4 6 7 8 9

Position 2 holds 4, so the 3rd smallest value is 4. In code, you write k = 2 for "3rd smallest". This is the most common source of mistakes in this topic, and the section on common mistakes shows what happens when you forget it.

The median is the middle value. For seven numbers the median is the 4th smallest, which is position 3, the value 6. For an even number of values, there are two middle values. This lesson uses the lower one, which is position (n - 1) / 2.

The problem is this. Given a list and a number k, return the value at position k in sorted order. The list may not be sorted, and you do not want to sort it.

The idea: one partition tells you where to look

Recall what partitioning does. You pick one value as the pivot. You rearrange the list so that every value smaller than the pivot is on its left and every value bigger is on its right. The pivot then lands at a final position, which this lesson calls p. The quick sort lesson shows each swap in detail, so this lesson uses only the result.

After one partition, you know three things.

• If k equals p, the pivot is the answer. It is already in its sorted position.
• If k is smaller than p, the answer is on the left side. Every value on the right is bigger than the pivot, and the answer is smaller than the pivot, so the right side cannot hold it.
• If k is bigger than p, the answer is on the right side. The left side is smaller than the pivot, and the answer is bigger, so the left side cannot hold it.

Here is an everyday picture. Suppose 100 people stand in a line sorted by height, and you want the 10th shortest person. You pick one person at random, call them Ana, and ask everyone to step left if they are shorter than Ana and right if they are taller. Suppose Ana is the 40th shortest. Then the 10th shortest must be on the left, among the 39 people shorter than Ana. You can forget the 60 people on the right. You repeat the process only on the left group.

Each partition removes a part of the list that cannot contain the answer. Quick sort keeps both halves and sorts both. Quickselect keeps one half and drops the other. That saving is the whole idea.

The algorithm keeps two positions, lo and hi, which mark the current range of the list still under search. Each round it partitions lo through hi, compares k with p, and moves either hi or lo. The loop stops when k equals p.

The full program

The program below has the partition, the search, and a main function. The verbose flag prints one line per round so you can watch the range shrink. Copy it into the editor, leave the Input box empty and press Run.

The output is:

Finding the 3rd smallest (k = 2):
range 0..6, pivot 6 at index 3
range 0..2, pivot 1 at index 0
range 1..2, pivot 2 at index 1
range 2..2, pivot 4 at index 2
answer: 4
 
Checking every k against sorting:
k=0 quickselect=1 sorted=1
k=1 quickselect=2 sorted=2
k=2 quickselect=4 sorted=4
k=3 quickselect=6 sorted=6
k=4 quickselect=7 sorted=7
k=5 quickselect=8 sorted=8
k=6 quickselect=9 sorted=9

The second part of the output checks every k against a full sort. Every line matches. You can use this kind of check when you write your own version.

The function throws an error when k is outside the list. The code uses std::out_of_range from the <stdexcept> header. The section on common mistakes shows what happens when this error is not caught.

Worked example 1: the 3rd smallest of seven values

Use the list 7 2 9 4 1 8 6 and k = 2. The table follows the four rounds in the output above. Each row is one partition.

Look at round 1 in detail. The list starts as 7 2 9 4 1 8 6. The pivot is the last value, 6. Partitioning moves the values 2, 4 and 1 to the left of the pivot, and the values 7, 9 and 8 to the right. The pivot lands at index 3. The list after the partition is 2 4 1 6 9 8 7.

The value 6 is now in its sorted position, but we do not need it, because k = 2 is less than 3. The answer is in positions 0 to 2, which hold 2 4 1. The values 9, 8 and 7 at positions 4 to 6 are never looked at again.

Round 2 partitions 2 4 1 with pivot 1. It lands at index 0. The answer is at position 2, which is to the right of 0, so the search moves to positions 1 and 2.

Round 3 works on two values. The pivot is 2 and it lands at index 1. The answer is at position 2, so the search moves to position 2 alone.

Round 4 has one value, which is 4. It sits at position 2, and k is 2, so 4 is the answer.

Four rounds made 9 comparisons in total (6, 2, 1 and 0). Sorting seven values needs at least 13 comparisons in the worst case, and on a list of a million values the saving is far larger.

Worked example 2: the third highest score with repeated values

Teachers and game boards often need the top few values, not the bottom. The top value is the largest, which is the value at position n - 1 in sorted order. The third highest is at position n - 3. If you have six scores, the third highest is at position 6 - 3 = 3.

Here is a list of six scores with a repeated 92:

88 92 75 92 60 81

Sorted, it is 60 75 81 88 92 92. Position 3 holds 88, so the third highest score is 88. The repeated 92 counts as two separate values, so the highest score is 92, the second highest is also 92, and the third highest is 88.

The program below asks for position n - 3 and prints the result. It also prints the list after the call, to show that the list was rearranged.

The output is:

third highest score: 88
scores after the call: 75 60 81 88 92 92 

The second line shows that the order has changed. Quickselect rearranges the list it is given. The values are all still there, but they are not in the original order. The scores vector is passed by reference, so the caller sees the change. If you need the original order, pass a copy.

The rule to take from this example is that the same code handles the largest and the smallest. You only change k. Position k counts from the smallest value, so the k-th largest is at position n - k.

Worked example 3: the worst case with sorted input

The average speed of quickselect depends on the pivot. The partition in this lesson uses the last value as the pivot. Now consider a list that is already sorted, such as 1 2 3 4 5 6 7 8, and search for the median.

Partitioning a sorted list around its last value does not split it. Every other value is smaller than the last value, so every value stays on the left, and the pivot lands at the far right end. Only one value is removed each round. The search has to do the partition again on a list that is one value shorter, and then again, and again.

The program below counts comparisons. Each comparison is one check of a[j] < pivot. It runs the same search twice: once with the last value as the pivot, and once with a random pivot. The random pivot swaps a random value in the range into the last position before the partition. The mt19937 generator is in the <random> header.

The output is:

n=8 median=5 (5) last-pivot comparisons=22 random-pivot comparisons=13
n=100 median=51 (51) last-pivot comparisons=3725 random-pivot comparisons=361
n=1000 median=501 (501) last-pivot comparisons=374750 random-pivot comparisons=1835

The random-pivot counts come from the standard library's random number code, so another compiler can print different ones. Check the n = 8 line by hand. The first partition runs on all 8 values and makes 7 comparisons. The pivot 8 lands at index 7, which is to the right of the median position 4, so the search goes left over 7 values. That partition makes 6 comparisons, and the pivot 7 lands at index 6, still right of 4. The search goes left over 6 values. That partition makes 5 comparisons, and the pivot 6 lands at index 5. The search goes left over 5 values. That partition makes 4 comparisons, and the pivot 5 lands at index 4, which equals k, so the search stops. The total is 7 + 6 + 5 + 4 = 22.

For n = 1000, the ranges go from 1000 values down to 501 values, and each one makes one comparison fewer than its size. The sum of 999 down to 500 is 374750, which matches the output exactly. In general, this worst case costs about three eighths of n squared, because the sum of the sizes from n down to n / 2 is about that much.

The meaning of the growth matters more than the exact number. The notation for this is O(n squared). It means that when n doubles, the work becomes about four times bigger. Going from 100 values to 1000 values made the work about 100 times bigger, which is the square of the change in size.

The random pivot reorders the list, and it changes the chance of a bad split. With a random pivot, a sorted list gives no advantage and no penalty. The count for n = 1000 is 1835, which is far below 374750.

Average speed: why it is linear

The average case is what you should expect from a random pivot. Each round partitions the current range, which takes about as many comparisons as the range has values. The question is how fast the range shrinks.

A random pivot usually lands somewhere in the middle of the range, not at an end. The part you keep is therefore a fixed fraction of the current size, on average. Each round removes a share of what remains, so the sizes shrink like a geometric series: n, then a fraction of n, then a smaller fraction, and so on. The total work of a geometric series with a fixed fraction is a fixed multiple of n. That is what linear means here: the work grows in step with n, with a constant factor in front.

The program below measures this. It uses a random pivot and random input, runs 50 trials for each size, and reports the average number of comparisons. The value k = 0 asks for the smallest value, and k = n / 2 asks for the median. The code is the same as the random-pivot version above, with the trial loop added.

The output from one run is:

n=1000 k=0 average comparisons=2034.32 per value=2.03432
n=1000 k=500 average comparisons=3312.5 per value=3.3125
n=10000 k=0 average comparisons=20978.8 per value=2.09788
n=10000 k=5000 average comparisons=35469 per value=3.5469
n=100000 k=0 average comparisons=191464 per value=1.91464
n=100000 k=50000 average comparisons=332991 per value=3.32991

The program uses a fixed seed, so every run with the same C++ library prints these same numbers. Different seeds give slightly different averages. For the smallest value, the average is about 2 comparisons per value. For the median, it is about 3.3 to 3.5 comparisons per value. The count per value does not grow as n grows from 1000 to 100000. That is the linear average.

For comparison, sorting 100000 values with about n times log2 n comparisons takes roughly 1.7 million comparisons. The median search above took about 333000. The gap grows as n grows.

Why is the minimum cheaper than the median? Finding the smallest value always keeps the left side, which is on average half the range. Finding the median keeps whichever side holds the middle, which is on average about three quarters of the range, so the range shrinks more slowly.

Using the standard library

C++ has a ready-made version. std::nth_element is in the <algorithm> header. You give it the start of the list, the position you want, and the end of the list. It rearranges the list so that the value at the position you named is the one that would be there if the list were sorted. Values before that position are not bigger than it, and values after it are not smaller.

The output is:

3rd smallest: 4

The C++ standard asks for linear time on average from std::nth_element. Use it in real code, because it is tested and maintained. Writing quickselect yourself is still worth doing, because it shows the idea clearly, and interviewers often ask you to write it from scratch.

Common mistakes

Off by one in k. The most common mistake is to count from 1 when k counts from 0. The list 7 2 9 4 1 8 6 has the 3rd smallest value at position 2. From the output above, k=2 returns 4 and k=3 returns 6. If you ask for the third value and pass 3, you get the fourth.

Passing a position outside the list. If k is -1 or equal to the list size, no position exists. The lesson's function throws an error. If you do not catch it, the program stops with this output, which is what the first program prints if you call quickselect with k = 7 and nothing catches the error:

terminate called after throwing an instance of 'std::out_of_range'
  what():  k must be between 0 and size - 1

The exit code of the program is 134, which means it was stopped by an abort signal. Catch the error with a try block if your program must keep running, or check k before you call the function.

Passing a const list. The function changes the list, so its parameter is not const. Passing a const vector gives this error from g++ 15:

bad_const.cpp: In function ‘int main()’:
bad_const.cpp:6:24: error: binding reference of type ‘std::vector<int>&’ to ‘const std::vector<int>’ discards qualifiers
    6 |     return quickselect(data, 1);
      |                        ^~~~
bad_const.cpp:3:30: note: initializing argument 1 of ‘int quickselect(std::vector<int>&, int)’
    3 | int quickselect(vector<int>& a, int k);
      |                 ~~~~~~~~~~~~~^

The last two lines point at the declaration of quickselect, where the parameter is not const. You have two fixes. Copy the list, as the sample above does, or take the list by value, as the random-pivot version does. The copy costs memory, but the caller keeps its original order.

Keeping the wrong edge. When the pivot is not the answer and the answer is on the left, the new hi must be p - 1, not p. The pivot is already known to be too big, so it must leave the range. If you write hi = p, the pivot stays in the range. With the two values 5 and 9, where the pivot 9 stays at index 1 and k = 0, the range never shrinks. A test run of that wrong code printed still looping after 6 steps, range 0..1 and would have continued forever without the step limit.

Unsigned positions. If you use size_t for hi, then p - 1 wraps around to a huge number when p is 0. The loop then reads positions far outside the list. This is undefined behaviour, which means the program may crash or print wrong values, with no clear message. Use int for positions, as the code in this lesson does, and convert the size with static_cast<int>.

Expecting the list to stay in order. Quickselect rearranges the list it is given, as worked example 2 shows. If you need the original list later, copy it first.

Many equal values with the last-value pivot. The partition in this lesson moves only values strictly smaller than the pivot to the left. If many values are equal to the pivot, they all stay on the right side, and the search removes one value per round. A list of 1000 copies of the value 7, searched for the median, took 375249 comparisons in a measured run with the same counting partition, and 2000 copies took 1500499. That is the same quadratic pattern as sorted input. The quick sort lesson in this module covers how to handle many equal values.

Practice

Exercise 1. Partition the list 4 1 3 2 with the last value as the pivot, using the partition function from this lesson. What is the final index of the pivot, and what does the list look like after the partition?

Show the answer

The pivot is 2. The function moves 1 to the front, then swaps the pivot into index 1. The pivot lands at index 1, and the list is 1 2 3 4.

Exercise 2. The scores are 10 2 8 6 4. Which k should you pass to quickselect to find the third largest score, and what is that score?

Show the answer

Pass k = 2. The list has 5 values, so the third largest is at position 5 - 3 = 2 when counting from the smallest. Sorted, the list is 2 4 6 8 10, and position 2 holds 6. The third largest score is 6.

Exercise 3. Use the last-value partition on the sorted list 1 2 3 4 5 and search for k = 0, the smallest value. How many comparisons does the search make in total? Explain why.

Show the answer

It makes 10 comparisons. The first partition has pivot 5 and makes 4 comparisons. The pivot lands at index 4, so the search goes left over 4 values. The next partition makes 3 comparisons, then 2, then 1. The total is 4 + 3 + 2 + 1 = 10. Each round removes only the largest value, which is the worst case for a last-value pivot on sorted input.

Exercise 4. Write a function kth_largest(vector<int>& a, int k) that returns the k-th largest value, where k = 1 means the largest. Use quickselect from this lesson and do not sort the list.

Show the answer

The code below is one correct answer. It converts the 1-based rank k into a 0-based position from the smallest value, which is n - k.

int kth_largest(vector<int>& a, int k) {
    return quickselect(a, static_cast<int>(a.size()) - k);
}

Check it with n = 5 and k = 1. The position is 5 - 1 = 4, which is the last position in sorted order, so the function returns the largest value.

Exercise 5. For a list of six values, which position gives the lower median? Which position gives the upper median? Give the formula for each.

Show the answer

The lower median of six values is the third smallest, at position 2. The upper median is the fourth smallest, at position 3. The formula for the lower median is (n - 1) / 2, which gives 5 / 2 = 2 with integer division. The formula n / 2 gives 3, which is the upper median.

Summary

• Quickselect finds the k-th smallest value by partitioning once and searching only the side that holds the answer.
• Positions count from 0, so the 3rd smallest value has k = 2.
• Each round removes a share of the list, so the average work is linear: about 2 comparisons per value for the minimum and about 3.3 to 3.5 for the median in the measured runs.
• With a fixed last-value pivot, sorted input or many equal values can make the work grow with the square of n.
• A random pivot removes the bad case for sorted input, and std::nth_element provides the same search in the standard library.