Distributional analysis of swaps in Quick Select

We investigate the number of swaps made by Quick Select (a variant of Quick Sort for finding order statistics) to find an element with a randomly selected rank under realistic partition algorithms such as Lomuto’s or Hoare’s. This kind of grand average provides a smoothing over all individual distributions for specific fixed order statistics. The grand distribution for the number of swaps (when suitably scaled) is a perpetuity (a sum of products of independent mixed continuous random variables supported on the interval (0,1)). The tool for this proof is contraction in the Wasserstein metric space, and identifying the limit as the fixed-point solution of a distributional equation. The same methodology carries over when Quick Select is commissioned to find an extremal order statistic (of a relatively small or relatively large rank) and the results are of similar nature. It is one of our purposes to show that analysis under different partition algorithms leads to different results.