Quickselect finds the th smallest value in an unsorted collection by partitioning around a pivot and continuing only in the group that contains the requested rank. It can extract a single loss threshold from a large scenario set without sorting every scenario. The returned value is the same order statistic that a full sort would put at position .
Find the block that contains the rank
Count ranks from 1 in ascending order. Tied values each occupy a position. For a pivot , split the active observations into groups strictly below, equal to and strictly above . Let count the observations below the pivot and count those equal to it.
- If , keep the lower group and search for the same rank.
- If , return . Every rank in the equal block has that value.
- If , keep the upper group and search for rank within it.
Three-way partitioning resolves all ties at the pivot in one pass. If the task requires a specific record among tied values, the ordering must also specify a tie-breaker such as record ID. Kiwiel, Partitioning schemes for quicksort and quickselect, §6.1.
Take eight toy losses of 9, 1, 8, 2, 7, 3, 6 and 6 USD. To find the fifth smallest, suppose the first pivot is 6. Three losses fall below it, two equal it and three exceed it. The two copies of 6 occupy ranks 4 and 5, so the answer is USD 6 after one partition.
Partitioning locates the requested rank inside the equal block. The larger losses can stay in the order 9, 8, 7.
How much work can a pivot save?
Each partition scans the active group. If a pivot is drawn uniformly from the remaining observations at each step, it has a constant chance of cutting the active group by a constant fraction or finding the answer. The expected work across those shrinking groups is , where is the initial sample size. The expectation is over pivot choices for a fixed input.
With distinct values, a run can repeatedly pick an extreme pivot on the side away from the target and discard just one observation at a time. Scanning groups of sizes gives worst-case time. Deterministic median-of-medians selection spends extra work choosing pivots that guarantee time in the worst case. MIT, Order Statistics, Blum et al., Time Bounds for Selection.
The quantile rule comes first
To compute a sample quantile, first specify how the probability maps to sample ranks. Inverting the empirical distribution uses rank for . At , the eight losses give rank 6 and a threshold of USD 7. Type 7 interpolation uses fractional rank . It goes a quarter of the way from the sixth-smallest loss, USD 7, to the seventh-smallest, USD 8, giving USD 7.25. Quickselect can retrieve the required observations for either rule. It changes the computation time while leaving the estimate and its sampling uncertainty unchanged. Hyndman and Fan, Sample Quantiles in Statistical Packages.
The SelfMadeQuant lesson Medians and Order Statistics: Quickselect traces the distinct-key case and shows how the target rank changes when the search moves to the upper group. The full lesson is for members.