Combinatorial analysis of quicksort algorithm. (English) Zbl 0685.68058

The average behaviour and higher moments of the distribution of the running times of the QUICKSORT algorithm are studied by applying the symbolic operator method. The exponential generating function of cost for the QUICKSORT algorithm is given. As practical illustration, for small lists (size \(\leq M)\) INSERTSORT was used within the QUICKSORT algorithm, and for sorting of lists of size \(<5,000\) the optimal value of M is between 10 to 15.
Reviewer: R.Klette


68P10 Searching and sorting
05A15 Exact enumeration problems, generating functions
68Q25 Analysis of algorithms and problem complexity


Full Text: DOI EuDML


[1] 1 A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[2] 2 L. COMTET, Analyse Combinatoire, P.U.F., Paris, 1970. Zbl0221.05002 · Zbl 0221.05002
[3] 3 P. FLAJOLET, Mathematical Analysis of Algorithms and Data Structures, I.N.R.I.A., Res. Rep., Vol. 400, 1985. · Zbl 0596.05007
[4] 4 P. FLAJOLET and C. PUECH, Partial match retrieval of multidimensional data, J.A.C.M. 33, Vol. 2, 1986, pp.371-407. MR835110
[5] 5 D. FOATA, La série génératrice exponentielle dans les problèmes d’énumération, S.M.S., Montréal University Press, 1974. Zbl0325.05007 MR505546 · Zbl 0325.05007
[6] 6 D. H. GREENE, Labelled Formal Languages and Their Uses, Ph. D. Thesis, 1983.
[7] 7 D. E. KNUTH, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Vol. 3, Sorting and searching, Addison Wesley, Reading, 1968, 1973. MR378456 · Zbl 0191.17903
[8] 8 M. REGNIER, A limiting Distribution for Quicksort, RAIRO, Th. Informatics and Applications (to appear). Zbl0677.68072 MR1020478 · Zbl 0677.68072
[9] 9 R. SEDGEWICK, Quicksort, Garland pub. co., New York, 1980.
[10] 10 J. M. STEYAERT, Complexité et structure des algorithmes, Thesis Paris, 1984.
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.