Strong concentration for Quicksort

ABSTRACT

Let Qn be the random number of comparisons made by quicksort in sorting n distinct keys, when we assume that all n! possible orderings are equally likely. Known results concerning moments for Qn do not show how rare it is for Qn to make large deviations from its mean. Here we give a good approximation to the probability of such a large deviation, and find that this probability is quite small. As well as the basic quicksort we consider the variant in which the partitioning key is chosen as the median of (2t+1) keys.

REFERENCES

• Dev86: Luc Devroye, A note on the height of binary search trees, Journal of the ACM (JACM), v.33 n.3, p.489-498, July 1986 [doi>10.1145/5925.5930]
• Hen89: P. Hennequin. Combinatorial analysis of quicksort algorithm. Theoretical In/ormatics and Applications, 23(3):317-333, 1989.
• Hoa61: C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
• Hoa62: C.A.R. Hoare. Quicksort. Computer J., 5:10-15, 1962.
• Knu73: Donald Knuth. The Art o/ Computer Programming. Addison-Wesley, first edition, 1973.
• McD89: Colin McDiarmid. On the method of bounded differences. In J Siemons, editor, Surveys in Combinatorics. London Math Society, 1989.
• Rég89: Mireille R~gnier. A limiting distribution for quicksort. Theoretical Informatics and Applications, 23(3):335-343, 1989.
• Rös: Uwe Rfsler.A limit theorem for quicksort. manuscript.
• Sed80: Robert Sedgewick. Quicksort. Garland Publishing Inc., first edition, 1980.
• Van70: M. H. van Emden, Increasing the efficiency of quicksort, Communications of the ACM, v.13 n.9, p.563-567, Sept. 1970 [doi>10.1145/362736.362753]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing

General Terms:
Measurement, Theory, Verification