Algorithms and data structures · Intermediate

Select one rank with three-way Quickselect

Track duplicate ranks and unexamined values while distinguishing input mutation, expected linear work and worst-case cost.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Select a rank without sorting everything
  2. Create a whole equal-pivot region
  3. Reinspect an element swapped from the far side
  4. Separate expected linear work from the quadratic worst case
  5. Know what remains unordered
  6. Inspect all four partition regions
  7. Select both middle ranks when the definition requires them
  8. Exercise: count ranks occupied by duplicates
  9. Ask Logeia about this articleCheck your understanding

Select a rank without sorting everything

In nine, two, seven, two, five, zero-based rank two is five: sorting gives two, two, five, seven, nine. Quickselect instead partitions around a pivot and continues only in the region containing the requested rank. It need not sort regions that cannot contain the answer. Returning the selected value does not promise that the whole array is ordered.

Duplicates occupy separate ranks. Selecting the third distinct value is a different task. For even-sized medians, specify whether the result is a lower middle value, an upper middle value or their arithmetic average. This function returns the value at one valid zero-based rank. Precise rank and duplicate conventions prevent a mathematically plausible answer from violating the caller's intended statistic.

Create a whole equal-pivot region

With pivot five, smaller values are two and two, the equal region contains five, and larger values are nine and seven. Two values are smaller, so rank two lies in the equal region and the answer is already known. Ranks zero and one continue left; three and four continue right. The code keeps global array indices, so it does not subtract a left-region size from k when moving right.

Three-way partitioning also handles repeated pivots cleanly. An all-seven array becomes one equal region in a single partition, answering every valid rank. During partitioning, track established smaller values, established equal values, unexamined values and established larger values. After swapping from the unexamined far end, that incoming element still needs inspection before advancing the scan index.

Compared with pivot 5ValuesZero-based ranks
Less2,20,1
Equal52
Greater9,7 (need not be sorted)3,4

Reinspect an element swapped from the far side

Within [lo,hi), lt, i and gt delimit partition state. A value below the pivot swaps with lt and advances both indices. A larger value swaps with the position just before gt, but i does not advance: the incoming value has not been examined. An equal value advances only i. When i reaches gt, the unexamined region is empty and all three regions satisfy their comparisons.

A seeded random generator chooses pivots from the current region. The function mutates its input, so callers preserving original order must pass a copy. Tests compare every rank of all ternary arrays of lengths one through six against sorted. Empty input and invalid ranks raise IndexError. Check the mutation contract alongside the partition invariant rather than treating selection as a read-only query.

python
import random
from itertools import product
def select(a,k,seed=7):
    if not 0<=k<len(a):raise IndexError(k)
    rng=random.Random(seed);lo=0;hi=len(a)
    while True:
        pivot=a[rng.randrange(lo,hi)];lt=lo;i=lo;gt=hi
        while i<gt:
            if a[i]<pivot:a[lt],a[i]=a[i],a[lt];lt+=1;i+=1
            elif a[i]>pivot:gt-=1;a[i],a[gt]=a[gt],a[i]
            else:i+=1
        if k<lt:hi=lt
        elif k>=gt:lo=gt
        else:return pivot
for n in range(1,7):
    for values in product(range(3),repeat=n):
        for k in range(n):assert select(list(values),k)==sorted(values)[k]
try:select([],0)
except IndexError:pass
else:raise AssertionError('invalid rank accepted')
print('all ternary arrays lengths1..6 and every rank passed')

Separate expected linear work from the quadratic worst case

Partitioning scans the current region. Reasonably balanced choices lead to a series resembling n plus n/2 plus n/4, while randomized pivot analysis gives expected O(n) selection time. Repeatedly extreme pivots can instead produce n plus n minus one and so on, yielding an O(n squared) worst case. A successful fixed-seed run does not eliminate that possibility.

This iterative implementation avoids a deep recursion stack and partitions in place, but a caller-created copy adds linear storage. Other selection implementations may use different pivot policies or worst-case fallbacks. Read their actual contracts rather than transferring guarantees from a library name to this teaching code. Distinguish expected performance over random choices, measurements on one input and the worst-case bound over possible executions.

Know what remains unordered

A returned rank value does not imply that every earlier position is fully sorted. Partitioning establishes relative regions while leaving internal order unresolved. Extracting a group of smallest values and displaying that group in sorted order are different output requirements; the second may need an additional sort. Do not extend a value-only function's promise to every other array position.

For repeated rank queries, compare selection on separate copies with one complete sort followed by indexed access. Query count, mutation permission and worst-case latency requirements can change the better choice. Record whether copying and preparation are included in timings. Doing less theoretical work for one rank does not establish that selection always makes the complete application faster under every workload.

Inspect all four partition regions

During partitioning, [lo,lt) is smaller, [lt,i) equal, [i,gt) unexamined and [gt,hi) greater. Swapping a large value right brings an unclassified value to i, so reexamine it. A small-value swap instead uses the established equal-region boundary and advances both indices.

Checking intermediate invariants on tiny inputs can expose errors that final examples miss. A debug version may assert each region after every exchange, but its additional scans must not be timed as if they were part of the optimized ordinary loop. Separate validation instrumentation from the computational cost being claimed. The proof and the measurements should identify exactly which version they describe.

With duplicates, the answer need not have exactly k strictly smaller elements. It must equal the value at sorted index k, which is why reaching the equal partition can finish the search.

Select both middle ranks when the definition requires them

For an even length of six, defining the median as the average of the two middle values requires ranks two and three. Duplicates occupy both ranks independently. A straightforward two-selection implementation must decide whether to preserve the original array and whether to reuse the first partition state.

The average need not be an integer, and a fixed-width sum can overflow before division. This value-at-one-rank function does not define median rounding or output type. Add and test those requirements at the caller boundary. Correct selection of one rank and correct construction of the product's median result are separate properties, even when one is used as a component of the other.

Exercise: count ranks occupied by duplicates

For four, one, four, two, four, three, select zero-based rank three with pivot four. The smaller region has three elements, one, two and three; the equal region has three fours; the greater region is empty. Ranks three, four and five all return four. Rank three means the fourth item including duplicates, not the fourth distinct value.

Changing the requested rank to two continues into the smaller three-element region and returns three. Counting the equal group as one item would shift later ranks incorrectly. Finally, an empty array has no valid rank zero and must raise the documented exception. Explain the rank contract, partition intervals, duplicate multiplicity and expected versus worst-case cost as one consistent algorithm.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path