Quickselect

An amber river stone singled out by sunlight among scattered, unordered stones.

Quickselect finds the value at a chosen rank without sorting the entire collection, using pivot-based partitioning.

What is quickselect?

Quickselect finds the value at a chosen rank in an unsorted collection. For example, it can find the smallest value, the median, or the tenth-smallest value without sorting every item.

It uses the same idea as quick sort: choose a pivot and partition values around it. But quickselect continues only in the part that can contain the answer.

What does “fourth-smallest” mean?

Rank counts positions in the sorted order, starting with the smallest. In the list 9, 2, 7, 4, 1, 8, 3, the fourth-smallest value is 4, even though the list itself is not sorted.

If a program uses zero-based indexes, rank four is index three. For the k-th largest value in a collection of n values, with k counted from one, select zero-based index n - k.

With repeated values, equal items occupy several ranks. A selection algorithm should define whether it returns a value or a particular item when several items have the same value. Quickselect usually returns the value at the requested rank.

How does quickselect work?

Quickselect keeps a range of values that still contains the requested rank:

  1. Choose a pivot from the current range.
  2. Partition the range into values less than the pivot, equal to it, and greater than it.
  3. Count the positions covered by each group.
  4. If the requested rank lies in the equal group, return the pivot.
  5. Otherwise, continue only in the lower or higher group that contains the rank.

For the example 9, 2, 7, 4, 1, 8, 3, suppose the pivot is 4. Partitioning gives lower values 2, 1, 3, the pivot 4, and higher values 9, 7, 8. Three values are below 4, so 4 is the fourth-smallest value. There is no need to order either group.

A different pivot might not reveal the answer immediately. Quickselect then discards the group that cannot contain the requested rank and repeats the process on the remaining group.

A simple version

The following pseudocode uses a three-way partition. Its rank, k, is zero-based. The partition returns less_end, the first index not less than the pivot, and equal_end, the last index equal to it.

quickselect(values, k)
    low = 0
    high = length(values) - 1

    while low <= high
        pivot = choose_random_value(values, low, high)
        (less_end, equal_end) =
            partition_into_less_equal_greater(values, low, high, pivot)

        if k < less_end
            high = less_end - 1
        else if k <= equal_end
            return values[k]
        else
            low = equal_end + 1

The partition operation moves values less than the pivot to the left, equal values into the middle, and greater values to the right. The exact positions depend on the implementation, but the key point is that the next pass handles only one of those regions.

Work through three examples

The example controls let you switch between three cases:

  • Distinct values: find the fourth-smallest value in [9, 2, 7, 4, 1, 8, 3]. The answer is 4.
  • Median: find the middle value in [9, 1, 6, 3, 8, 2, 7, 4, 5]. The answer is 5.
  • Repeated values: find the fourth-smallest value in [5, 2, 5, 1, 5, 3]. The answer is 5; the requested rank falls within the group of equal values.

Step through each reference run to see how the active range narrows. In the scratch pad, enter an array and choose the rank you want. Make the partition decisions one action at a time, then compare your sequence with the reference run.

Loading interactive comparison…

Why is it faster than sorting?

Sorting arranges every value. Quickselect needs to place only enough values to identify one rank.

A partition pass examines the current range once. With a randomly chosen pivot, the expected total work is O(n) for n values. It may still take O(n²) in the worst case if the pivots repeatedly leave almost all values in the active range.

An in-place implementation uses only a small amount of extra storage beyond the array. Some implementations use recursion, which adds call-stack space; an iterative version avoids that stack.

When is quickselect useful?

Quickselect is useful when you need a rank-based result but do not need the whole collection sorted. Examples include:

  • Finding a median or percentile
  • Keeping the k smallest or largest values
  • Choosing a threshold value for a later calculation

If you need many ranks or the values in sorted order, sorting once may be simpler. Quickselect can also rearrange the input array, so copy it first when the original order must be preserved.

What is the main idea?

Quickselect spends work only where the answer can still be. A pivot divides the collection, and the requested rank tells the algorithm which part to keep.

That is why selecting one value can take less work than sorting all of them.

References

Ai disclosure: written with the help of AI (ChatGPT). You are encouraged to point out errors and omissions.

Updated: 2026 Nov 18