Some Results on Asymptotic Behavior of the Recalls of Random Median Quicksort

Document Type : Original Scientific Paper

Authors

Department of Statistics, University of Zanjan, Zanjan, I. R. Iran

Abstract

This paper investigates the asymptotic behavior of the number of recalls  Xn of the Random Median Quicksort algorithm in order to sort a list of n distinct numbers. As  n→∞, we provide the asymptotics of the expectation and variance of the recalls. Furthermore, by utilizing a refined version of the contraction method for degenerate limits, we show the limiting distribution of Xn correctly normalized is Gaussian. The theoretical results are demonstrated by a simulation study.

Keywords


[1] C. J. Bell, An Investigation into the Principles of the Classification and Analysis of Data of an Automatic Digital Computer, Ph.D. Thesis, Leeds University, UK, 1965.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd Ed., MIT Press, USA, 2001.
[3] L. Devroye, Limit laws for local counters in random binary search trees, Random Struct. Algor. 2 (1991) 303 − 316.
[4] P. Hennequin, Analyse Enmoyenne D’algorithmes, Tri Rapide et Arbres de Recherche, Ph.D. Thesis, École Polytechnique, Palaiseau, 1991.
[5] C. A. R. Hoare, Quicksort, Comput. J. 5 (1962) 10 − 15.
[6] C. Holmgren and S. Janson, Limit laws for functions of fringe trees for binary search trees and random recursive trees, Electron. J. Probab. 20 (4) (2015) 1 − 51.
[7] V. Iliopoulos, A note on multipivot Quicksort, J. Info. Optim. Sci. 39 (2018) 1139 − 1147.
[8]  V. Iliopoulos, The Quicksort Algorithm and Related Topics, PhD Thesis, Department of Mathematical Sciences, University of Essex, 2013.
[9] D. E. Knuth, The Art of Computer Programming, Vol. III: Sorting and Searching, 2nd Ed., Addison-Wesley Publishing Company, Reading, MA, USA, 1998.
[10] M. Javanian and U. Röesler, Median Quicksort process, Probab. Eng. Inf. Sci. (2021) Submitted.
[11] H. M. Mahmoud, Sorting: A Distribution Theory, John Wiley & Sons, New York, 2000.
[12] R. Neininger and L. Rüschendorf, On the contraction method with degenerate limit equation, Ann. Probab. 32 (3B) (2004) 2838 − 2856.
[13] R. Neininger, Refined Quicksort asymptotics, Random Struct. Algor. 46 (2015) 346 − 361.
[14] H. M. Okasha and U. Röesler, Asymptotic distribution for random median Quicksort, J. Discrete Algor. 5 (2007) 592 − 608.
[15] S. Rachev and L. Rüschendorf, Probability metrics and recursive algorithms, Adv. Appl. Probab. 27 (1995) 770 − 799.
[16] S. Rachev, Probability Metrics and the Stability of Stochastic Models, John Wiley & Sons, New York, 1991.
[17] U. Röesler, A limit theorem for “Quicksort”, RAIRO Théor. Inform Appl. 25 (1991) 85 − 100.
[18] U. Röesler, On the analysis of stochastic divide and conquer algorithms, Algorithmica 29 (12) (2001) 238 − 261.
[19] U. Röesler and L. Rüschendorf, The contraction method for recursive algorithms, Algorithmica 29 (2001) 3 − 33.
[20] R. S. Scowen, Algorithm 271: Quickersort, Commun. ACM 8 (1965) 669−670.
[21] R. Sedgewick, Quicksort, Ph.D. Thesis, Garland Pub. Co., New York, 1980.
[22] R. C. Singleton, Algorithm 347: An efficient algorithm for sorting with minimal storage, Commun. ACM 12 (3) (1969) 185 − 186.
[23] K. H. Tan, An Asymptotic Analysis of the Number of Comparisons in Multipartition Quicksort, Ph.D. thesis, Carnegie Mellon University, 1993.
[24] A. Walker and D. Wood, Locally balanced binary trees, Comput. J. 19 (1976) 322 − 325.
[25] V. M. Zolotarev, Approximation of distributions of sums of independent random variables with values in infinite-dimensional spaces, Theory Probab. Appl. 21 (4) (1976) 721 − 737.