×

Analysis of quickselect under Yaroslavskiy’s dual-pivoting algorithm. (English) Zbl 1336.68052

Summary: There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved performance in Quicksort is not sustained in Quickselect; a variant of Quicksort for finding order statistics. We investigate the number of comparisons made by Quickselect to find a key with a randomly selected rank under Yaroslavskiy’s algorithm. This grand averaging is a smoothing operator over all individual distributions for specific fixed order statistics. We give the exact grand average. The grand distribution of the number of comparison (when suitably scaled) is given as the fixed-point solution of a distributional equation of a contraction in the Zolotarev metric space. Our investigation shows that Quickselect under older partitioning methods slightly outperforms Quickselect under Yaroslavskiy’s algorithm, for an order statistic of a random rank. Similar results are obtained for extremal order statistics, where again we find the exact average, and the distribution for the number of comparisons (when suitably scaled). Both limiting distributions are of perpetuities (a sum of products of independent mixed continuous random variables).

MSC:

68P10 Searching and sorting
60C05 Combinatorial probability
68P20 Information storage and retrieval of data

Software:

MaLiJAn; Find; Quicksort
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Hoare, CAR, Quicksort, Comput. J., 5, 10-16, (1962) · Zbl 0108.13601
[2] Hoare, CAR, Algorithm 65: find, Commun. ACM, 4, 321-322, (1961)
[3] Sedgewick, R, The analysis of quicksort programs, Acta Inform., 7, 327-355, (1977) · Zbl 0325.68016
[4] Wild, S., Nebel, M.E.: Average case analysis of Java 7’s dual pivot quicksort. In: Epstein, L., Ferragina, P. (eds.) ESA 2012, LNCS, vol. 7501, pp. 825-836. Springer, Berlin (2012) · Zbl 1337.68083
[5] Kirschenhofer, P; Prodinger, H, Comparisons in hoare’s find algorithm, Comb. Probab. Comput., 7, 111-120, (1998) · Zbl 0892.68021
[6] Knuth, D.E.: The Art Of Computer Programming: Searching and Sorting, 2nd edn. Addison Wesley, Reading (1998) · Zbl 0883.68015
[7] Fill, JA, Distributional convergence for the number of symbol comparisons used by quicksort, Ann. Appl. Probab., 23, 1129-1147, (2013) · Zbl 1272.68482
[8] Mahmoud, HM, Distributional analysis of swaps in quick select, Theor. Comput. Sci., 411, 1763-1769, (2010) · Zbl 1192.68201
[9] Martínez, C; Prodinger, H, Moves and displacements of particular elements in quicksort, Theor. Comput. Sci., 410, 2279-2284, (2009) · Zbl 1166.68045
[10] Wild, S., Nebel, M.E., Neininger, R.: Average case and distributional analysis of Java 7’s dual pivot quicksort. ACM Trans. Algorithms (accepted for publication). http://arxiv.org/abs/1304.0988 · Zbl 0853.60033
[11] Hennequin, P.: Analyse en moyenne d’algorithmes: tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau (1991)
[12] Sedgewick, R.: Quicksort. PhD Thesis, Stanford University (1975) · Zbl 0108.13601
[13] Hennequin, P, Combinatorial analysis of quicksort algorithm, Informatique théorique et applications, 23, 317-333, (1989) · Zbl 0685.68058
[14] Bentley, J, Programming pearls: how to sort, Commun. ACM, 27, 287-291, (1984)
[15] Chung, K.L.: A Course in Probability Theory, 3rd edn. Academic Press, New York (2001)
[16] Embrechts, P., Klüppelberg, C., Mikosch, T.: Modelling Extremal Events. Springer, Berlin (1997) · Zbl 0873.62116
[17] Alsmeyer, G; Iksanov, A; Rösler, U, On distributional properties of perpetuities, J. Theor. Probab., 22, 666-682, (2009) · Zbl 1173.60309
[18] Wild, S.: Java 7’s Dual Pivot Quicksort. Master thesis, University of Kaiserslautern (2012) · Zbl 1337.68083
[19] Mahmoud, HM; Modarres, R; Smythe, RT, Analysis of quickselect: an algorithm for order statistics, Informatique théorique et applications, 29, 255-276, (1995) · Zbl 0838.68029
[20] Lent, J; Mahmoud, HM, Average-case analysis of multiple quickselect: an algorithm for finding order statistics, Stat. Probab. Lett., 28, 299-310, (1996) · Zbl 0854.62052
[21] Prodinger, H, Multiple quickselect—hoare’s find algorithm for several elements, Inf. Process. Lett., 56, 123-129, (1995) · Zbl 0875.68313
[22] Panholzer, A; Prodinger, H, A generating functions approach for the analysis of grand averages for multiple QUICKSELECT, Random Struct. Algorithms, 13, 189-209, (1998) · Zbl 0959.68513
[23] Rösler, U, A limit theorem for “quicksort”, Informatique théorique et applications, 25, 85-100, (1991) · Zbl 0718.68026
[24] Rachev, ST; Rüschendorf, L, Probability metrics and recursive algorithms, Adv. Appl. Probab., 27, 770-799, (1995) · Zbl 0829.60094
[25] Neininger, R, On a multivariate contraction method for random recursive structures with applications to quicksort, Random Struct. Algorithms, 19, 498-524, (2001) · Zbl 0990.68054
[26] Neininger, R; Rüschendorf, L, A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14, 378-418, (2004) · Zbl 1041.60024
[27] Rösler, U, On the analysis of stochastic divide and conquer algorithms, Algorithmica, 29, 238-261, (2001) · Zbl 0967.68168
[28] Rösler, U; Rüschendorf, L, The contraction method for recursive algorithms, Algorithmica, 29, 3-33, (2001) · Zbl 0967.68166
[29] Grübel, R; Rösler, U, Asymptotic distribution theory for hoare’s selection algorithm, Adv. Appl. Probab., 28, 252-269, (1996) · Zbl 0853.60033
[30] Rösler, U, QUICKSELECT revisited, J. Iran. Stat. Inst., 3, 271-296, (2004) · Zbl 06657090
[31] Grübel, R, Hoare’s selection algorithm: a Markov chain approach, J. Appl. Probab., 35, 36-45, (1998) · Zbl 0913.60059
[32] Hwang, H.K., Tsai, T.H.: Quickselect and Dickman function. Comb. Probab. Comput. 11, 353-371 (2000) · Zbl 1008.68044
[33] Aumüller, M., Dietzfelbinger, M.: Optimal partitioning for dual pivot quicksort (2013). http://arxiv.org/abs/1303.5217 · Zbl 1272.68482
[34] Martínez, C; Panario, D; Viola, A, Adaptive sampling strategies for quickselects, ACM Trans. Algorithms, 6, 1-45, (2010) · Zbl 1300.68022
[35] Martínez, C; Roura, S, Optimal sampling strategies in quicksort and quickselect, SIAM J. Comput., 31, 683, (2001) · Zbl 0996.68038
[36] Wild, S., Nebel, M.E., Reitzig, R., Laube, U.: Engineering Java 7’s dual pivot quicksort using MaLiJAn. In: Sanders, P., Zeh, N. (eds.) ALENEX 2013, pp. 55-69. SIAM (2013) · Zbl 1166.68045
[37] Fill, JA; Nakama, T, Analysis of the expected number of bit comparisons required by quickselect, Algorithmica, 58, 730-769, (2009) · Zbl 1202.68128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.