×

Using nonlinear difference equations to study Quicksort algorithms. (English) Zbl 1433.68113

Summary: Using nonlinear difference equations, combined with symbolic computations, we make a detailed study of the running times of numerous variants of the celebrated Quicksort algorithms, where we consider the variants of single-pivot and multi-pivot Quicksort algorithms as discrete probability problems. With nonlinear difference equations, recurrence relations and experimental mathematics techniques, explicit expressions for expectations, variances and even higher moments of their numbers of comparisons and swaps can be obtained. For some variants, Monte Carlo experiments are performed, the numerical results are demonstrated and the scaled limiting distribution is also discussed.

MSC:

68P10 Searching and sorting
39A60 Applications of difference equations
68R05 Combinatorics in computer science
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cramer, M., A note concerning the limit distribution of the quicksort algorithm, Informatique Theériques et Applications, 30, 195-207 (1996) · Zbl 0860.68052 · doi:10.1051/ita/1996300301951
[2] Durand, M., Asymptotic analysis of an optimized Quicksort algorithm, Inform. Proc. Lett., 85, 2, 73-77 (2003) · Zbl 1042.68119 · doi:10.1016/S0020-0190(02)00351-4
[3] Ekhad, S.B. and Zeilberger, D., A detailed analysis of Quicksort running time, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger. Available at http://www.math.rutgers.edu/zeilberg/pj.html. Direct url:http://sites.math.rutgers.edu/zeilberg/mamarim/mamarimhtml/qsort.html. Also in:https://arxiv.org/abs/1903.03708.
[4] Ekhad, S.B. and Zeilberger, D., Explicit expressions for the variance and higher moments of the size of a simultaneous core partition and its limiting distribution, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger. Available at http://www.math.rutgers.edu/zeilberg/pj.html. Direct url: http://www.math.rutgers.edu/zeilberg/mamarim/mamarimhtml/stcore.html. Also in: https://arxiv.org/abs/1508.07637.
[5] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley · Zbl 0668.00003
[6] Hennequin, P., Combinatorial analysis of Quicksort algorithm, RAIRO Theor. Inform. Appl., 23, 3, 317-333 (1989) · Zbl 0685.68058 · doi:10.1051/ita/1989230303171
[7] Hoare, C. A.R., Quicksort, Comput. J., 5, 1, 10-15 (1962) · Zbl 0100.13201 · doi:10.1093/comjnl/5.1.10
[8] Iliopoulos, V., The Quicksort algorithm and related topics. Available at https://arxiv.org/abs/1503.02504.
[9] Iliopoulos, V., A note on multipivot Quicksort, J. Inf. Optim. Sci., 39, 5, 1139-1147 (2018)
[10] Iliopoulos, V.; Penman, D. B., Dual pivot quicksort, Discrete Math. Algorithms Appl., 04, 3 (2012) · Zbl 1291.68158 · doi:10.1142/S1793830912500413
[11] Knuth, D. E., The Art of Computer Programming, Volume 3: Sorting and Searching (1973), Addison-Wesley · Zbl 0302.68010
[12] Kauers, M.; Paule, P., The Concrete Tetrahedron (2011), Springer · Zbl 1225.00001
[13] Kirschenhofer, P.; Prodinger, H.; Martinez, C., Analysis of Hoare’s find algorithm with median-of-three partition, Random Struct. Algorithms, 10, 1-2, 143-156 (1997) · Zbl 0867.68034 · doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<143::AID-RSA7>3.0.CO;2-V
[14] Knessl, C.; Szpankowski, W., Quicksort algorithm again revisited, Discrete Math. Theor. Comput. Sci., 3, 43-64 (1999) · Zbl 0947.68042
[15] Panholzer, A., Analysis of multiple quickselect variants, Theor. Comput. Sci., 302, 1-3, 45-91 (2003) · Zbl 1044.68034 · doi:10.1016/S0304-3975(02)00729-6
[16] Schneider, C., The Summation package Sigma. A Mathematica package available from https://www3.risc.jku.at/research/combinat/software/Sigma/index.php. · Zbl 1066.68164
[17] Schneider, C., Symbolic summation assists combinatorics, Sem. Lothar. Combin., 56 (2007) · Zbl 1188.05001
[18] , Quicksort. Available at https://en.wikipedia.org/wiki/Quicksort.
[19] Zeilberger, D., A holonomic systems approach to special functions, J. Comput. Appl. Math., 32, 321-368 (1990) · Zbl 0738.33001 · doi:10.1016/0377-0427(90)90042-X
[20] Zeilberger, D., HISTABRUT: A maple package for symbol-crunching in probability theory, the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, posted Aug. 25, 2010. Available at http://www.math.rutgers.edu/zeilberg/mamarim/mamarimhtml/histabrut.html.
[21] Zeilberger, D., Symbolic moment calculus I.: Foundations and permutation pattern statistics, Ann. Comb., 8, 369-378 (2004) · Zbl 1053.05005 · doi:10.1007/s00026-004-0226-2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.