Adaptive Sampling Strategies for Quickselect

作     者：Martinez, Conrado Panario, Daniel Viola, Alfredo 

作者机构：Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain Carleton Univ Sch Math & Stat Ottawa ON K1S 5B6 Canada Univ Republica Inst Computac Montevideo Uruguay 

出 版 物：《ACM TRANSACTIONS ON ALGORITHMS》 (ACM Trans. Algorithms)

年 卷 期：2010年第6卷第3期

页      面：1–45页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：EU [IST-1999-14186] Spanish Ministry of Science and Technology [TIC2002-00190] NSERC of Canada Proyecto de Investigacion CSIC fondos 

主　　题：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.