Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Quickselect — where it appears

A selection algorithm that partitions around a pivot as quicksort does but continues only into the side holding the rank it wants. With random pivots it finds the element of a given rank in a linear number of comparisons on average, without sorting the rest.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

randomised pivot164 random bits2.96 ±23%median of mediansno random bits7.94 ±2%0.04.38.6comparisons per element — bar is the range over seeds, tick is the mean30 seeds, n = 4,001, median2.68× the mean, 14× the spread

What derandomising costs

Randomised selection finds the median of twenty thousand elements in 3.21 comparisons per element and median-of-medians takes 8.15 — two and a half times as many for the same answer, both linear. The number that decides between them is not either of those. It is that the first varies by 28% from seed to seed and the second by 1.6%.

bounds · Distribution 1101001,00010,00010⁵10⁶k, the elements the caller readscomparisonssort all, read kbuild a heap, pop kselect k, sort thoseincremental quicksortkeep the best k while scanningknockout tournamentdashed: the floorlabels at k = 1,00065,536 random distinct keysevery answer checked

The count of the part that was read

Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Randomised algorithmWorst caseComparison countDerandomisationDistributionGuaranteeHeapInformation floorLower boundMedian of mediansMerge sortOutput-sensitive

All concepts