Average-case analysis of moves in Quick Select
Hosam M. Mahmoud · 2009
We investigate the average number of moves made by Quick Select (a variant of Quick Sort for finding order statistics) to find an element with a randomly selected rank. This kind of grand average provides smoothing over all individual cases of a specific fixed order statistic. The variance of the number of moves involves intricate dependencies, and we only give reasonably tight bounds.