Adaptive Sampling Strategies for Quickselect

作者：Martinez Conrado^*; Panario Daniel; Viola Alfredo

来源：ACM Transactions on Algorithms, 2010, 6(3): 53.

DOI：10.1145/1798596.1798606

• Algorithms
• Theory
• Analytic combinatorics
• average-case analysis
• divide-and-conquer
• Find
• quickselect
• sampling
• selection

Quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. However, the following natural adaptive variant, which we call proportion-from-3, had not been previously analyzed: "choose as pivot the smallest of the sample if the relative rank of the sought element is below 1/3, the largest if the relative rank is above 2/3, and the median if the relative rank is between 1/3 and 2/3." We first analyze the average number of comparisons made when using proportion-from-2 and then for proportion-from-3. We also analyze nu-find, a generalization of proportion-from-3 with interval breakpoints at nu and 1 - nu. We show that there exists an optimal value of. and we also provide the range of values of nu where nu-find outperforms median-of-3. Then, we consider the average total cost of these strategies, which takes into account the cost of both comparisons and exchanges. Our results strongly suggest that a suitable implementation of nu-find could be the method of choice in a practical setting. We also study the behavior of proportion-from-s with s > 3 and in particular we show that proportion-from-s-like strategies are optimal when s -> 8.

• 出版日期2010-6