Average-case analysis of moves in Quick Select

The Sixth Workshop on Analytic Algorithmics and Combinatorics

Hosam M. Mahmoud

Others  :  http://www.siam.org/proceedings/analco/2009/anl09_006_mahmoudh.pdf
PID  :  18273

来源: CEUR

【 摘 要 】

We investigate the average number of moves made byQuick Select (a variant of Quick Sort for finding orderstatistics) to find an element with a randomly selectedrank. This kind of grand average provides smoothing overall individual cases of a specific fixed order statistic. Thevariance of the number of moves involves intricate dependencies, and we only give reasonably tight bounds.