{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T16:48:06Z","timestamp":1641487686161},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","award":["TIC2002-00190 (AEDRI II)"]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-1999-14186 (ALCOM-FT)"]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["238757"]},{"DOI":"10.13039\/501100003339","name":"Consejo Superior de Investigaciones Cient\u00edficas","doi-asserted-by":"publisher","award":["2000-20022002-2004"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,6]]},"abstract":"\n 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\n proportion-from-3<\/jats:italic>\n , had not been previously analyzed: \u201cchoose 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.\u201d We first analyze the average number of comparisons made when using proportion-from-2 and then for proportion-from-3. We also analyze \u03bd-find, a generalization of proportion-from-3 with interval breakpoints at \u03bd and 1-\u03bd. We show that there exists an optimal value of \u03bd and we also provide the range of values of \u03bd where \u03bd-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 \u03bd-find could be the method of choice in a practical setting. We also study the behavior of proportion-from-\n s<\/jats:italic>\n with\n s<\/jats:italic>\n >3 and in particular we show that proportion-from-\n s<\/jats:italic>\n -like strategies are optimal when\n s<\/jats:italic>\n \u2192\u221e.\n <\/jats:p>","DOI":"10.1145\/1798596.1798606","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T13:02:22Z","timestamp":1277816542000},"page":"1-45","source":"Crossref","is-referenced-by-count":8,"title":["Adaptive sampling strategies for quickselects"],"prefix":"10.1145","volume":"6","author":[{"given":"Conrado","family":"Mart\u00ednez","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"given":"Daniel","family":"Panario","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}]},{"given":"Alfredo","family":"Viola","sequence":"additional","affiliation":[{"name":"Universidad de la Rep\u00fablica, Casilla de Correo, Uruguay"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","first-page":"109","article-title":"Combinatorial aspects of C.A.R. Hoare's Find algorithm","volume":"5","author":"Anderson D.","year":"1992","journal-title":"Australasian J. Combin."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_3_1","unstructured":"Bleistein N. and Handelsman R. A. 1975. Asymptotic Expansions of Integrals. Dover New York. Bleistein N. and Handelsman R. A. 1975. Asymptotic Expansions of Integrals. Dover New York."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62047"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Daligault J. and Mart\u00ednez C. 2006. On the variance of quickselect. In Proceedings of the 8th ACM-SIAM Workshop on Algorithm Engineering and Experimennts (ALENEX) and the 3rd ACM-SIAM Workshop on Analytic Algorithmics and Cominatorics (ANALCO). R. Raman R. Sedgewick and M. Stallmann Eds. SIAM 205--210. Daligault J. and Mart\u00ednez C. 2006. On the variance of quickselect. In Proceedings of the 8th ACM-SIAM Workshop on Algorithm Engineering and Experimennts (ALENEX) and the 3rd ACM-SIAM Workshop on Analytic Algorithmics and Cominatorics (ANALCO). R. Raman R. Sedgewick and M. Stallmann Eds. SIAM 205--210.","DOI":"10.1137\/1.9781611972962.3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_2_1_7_1","unstructured":"Graham R. Knuth D. and Patashnik O. 1994. Concrete Mathematics 2nd Ed. Addison-Wesley Reading MA. Graham R. Knuth D. and Patashnik O. 1994. Concrete Mathematics 2nd Ed. Addison-Wesley Reading MA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita:1999112"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427920"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003325"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2%3C143::AID-RSA7%3E3.0.CO;2-V"},{"key":"e_1_2_1_14_1","unstructured":"Knof D. and R\u00f6sler U. 2007. The analysis of Find or perpetuities on Cadlag functions. Submitted to Discr. Math Theor. Comput. Sci. Knof D. and R\u00f6sler U. 2007. The analysis of Find or perpetuities on Cadlag functions. Submitted to Discr. Math Theor. Comput. Sci."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IFIP Congress Information Processing'71","author":"Knuth D.","year":"1972"},{"key":"e_1_2_1_16_1","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D.","edition":"2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032886"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90023-0"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM symposium on Discreate Algorithms (SODA). SIAM, 440--448","author":"Mart\u00ednez C."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199708)27:8%3C983::AID-SPE117%3E3.0.CO;2-#"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00729-6"},{"key":"e_1_2_1_23_1","unstructured":"Petkovsek M. Wilf H. S. and Zeilberger D. 1996. A = B. A. K. Peters Wellesley MA. http:\/\/www.math.upenn.edu\/~wilf\/Downld.html. Petkovsek M. Wilf H. S. and Zeilberger D. 1996. A = B. A. K. Peters Wellesley MA. http:\/\/www.math.upenn.edu\/~wilf\/Downld.html."},{"key":"e_1_2_1_24_1","unstructured":"Rainville E. Bedient P. and Bedient R. 1997. Elementary Differential Equations 8th Ed. Prentice Hall. Rainville E. Bedient P. and Bedient R. 1997. Elementary Differential Equations 8th Ed. Prentice Hall."},{"key":"e_1_2_1_25_1","unstructured":"Sedgewick R. 1978. Quicksort. Garland New York. Sedgewick R. 1978. Quicksort. Garland New York."},{"key":"e_1_2_1_26_1","unstructured":"Whittaker E. and Watson G. 1927. A Course of Modern Analysis 4th Ed. Cambridge University Press. Whittaker E. and Watson G. 1927. A Course of Modern Analysis 4th Ed. Cambridge University Press."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1798596.1798606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T12:45:47Z","timestamp":1613911547000},"score":1,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1798596.1798606"],"URL":"http:\/\/dx.doi.org\/10.1145\/1798596.1798606","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2010,6]]}}}