Skip to main content
SpringerLink
Log in

The analysis of Quicksort programs

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

The Quicksort sorting algorithm and its best variants are presented and analyzed. Results are derived which make it possible to obtain exact formulas describing the total expected running time of particular implementations on real computers of Quicksort and an improvement called the median-of-three modification. Detailed analysis of the effect of an implementation technique called loop unwrapping is presented. The paper is intended not only to present results of direct practical utility, but also to illustrate the intriguing mathematics which arises in the complete analysis of this important algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abramowitz, M., Stegun, I. A.: Handbook of mathematical functions. New York: Dover Publications 1970

    Google Scholar 

  2. Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The design and analysis of computer algorithms. Reading (Mass.): Addison-Wesley 1974

    Google Scholar 

  3. Boothroyd, J.: Sort of a section of the elements of an array by determining the rank of each element (Algorithm 25); Ordering the subscripts of an array section according to the magnitudes of the elements (Algorithm 26). Computer J. 10, pp308–310. [See also notes by R. S. Scowen in Computer J. 12, 408–409 (1969) and by A. D. Woodall in Computer J. 13 (1970)]

  4. Brawn, B. S., Gustavson, F. G., Mankin, E.: Sorting in a paging environment. Comm. ACM 13, 483–494 (1970)

    Google Scholar 

  5. Cocke, J., Schwartz, J. T.: Programming languages and their compilers. Preliminary notes. Courant Inst, of Math. Sciences, New York University (1970)

  6. Frazer, W. D., McKellar, A. C.: Samplesort: a sampling approach to minimal storage tree sorting. J. ACM 17, 496–507 (1970)

    Google Scholar 

  7. Hoare, C. A. R.: Partition (Algorithm 63); Quicksort (Algorithm 64); Find (Algorithm 65). Comm. ACM 4, 321–322 (1961). [See also certification by J. S. Hillmore in Comm. ACM 5, 439 (1962) and by B. Randell and L. J. Russell in Comm. ACM 6, 446 (1963)]

    Google Scholar 

  8. Hoare, C. A. R.: Quicksort. Computer J. 5, 10–15 (1962)

    Google Scholar 

  9. Knuth, D. E.: The art of computer programming 1: Fundamental algorithms. Reading (Mass.): Addison-Wesley 1968

    Google Scholar 

  10. Knuth, D. E.: The art of computer programming 2: Seminumerical algorithms. Reading (Mass.): Addison-Wesley 1969

    Google Scholar 

  11. Knuth, D. E.: The art of computer programming 3: Sorting and searching. Reading (Mass.): Addison-Wesley 1972

    Google Scholar 

  12. Knuth, D. E.: Structured programming with go to statements. Computing Surveys 6, 261–301 (1974)

    Google Scholar 

  13. Loeser, R.: Some performance tests of “quicksort” and descendants. Comm. ACM 17, 143–152 (1974)

    Google Scholar 

  14. Morris, R.: Some theorems on sorting. SIAM J. Appl. Math. 17, 1–6 (1969)

    Google Scholar 

  15. Rich, R. P.: Internal sorting methods illustrated with PL/I programs. Englewood Cliffs (N.J.): Prentice-Hall 1972

    Google Scholar 

  16. Scowen, R. S.: Quickersort (Algorithm 271). Comm. ACM 8, 669–670 (1965). (See also certification by C. R. Blair in Comm. ACM 9, 354 (1966))

    Google Scholar 

  17. Sedgewick, R.: Quicksort. Stanford University, Stanford Computer Science Report STAN-CS-75-492, Ph. D. Thesis, May 1975

  18. Sedgewick, R.: Quicksort with equal keys. SIAM J. Computing (to appear)

  19. Sedgewick, R.: Implementing Quicksort programs (to appear)

  20. Singleton, R. C.: An efficient algorithm for sorting with minimal storage (Algorithm 347). Comm. ACM 12, 185–187 (1969). [See also remarks by R. Griffin and K. A. Redish in Comm. ACM 13, 54 (1970) and by R. Peto in Comm. ACM 13, 624 (1970)]

    Google Scholar 

  21. van Emden, M. N.: Increasing the efficiency of quicksort (Algorithm 402). Comm. ACM 13, 693–694 (1970). [See also the article by the same name in Comm. ACM 13, 563–567 (1970)]

    Google Scholar 

  22. Wirth, N.: Algorithms + Data Structures = Programs. Englewood Cliffs (N. J.): Prentice-Hall 1976

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Program in Computer Science Division of Applied Mathematics, Brown University, 02912, Providence, Rhode Island, USA

    Robert Sedgewick

Authors
  1. Robert Sedgewick
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by the Fannie and John Hertz Foundation, and in part by the National Science Foundation Grants No. GJ-28074 and MC S75-23738

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sedgewick, R. The analysis of Quicksort programs. Acta Informatica 7, 327–355 (1977). https://doi.org/10.1007/BF00289467

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00289467

Keywords

Search

Navigation