Implementing Quicksort programs

Abstract

This paper is a practical study of how to implement the Quicksort sorting algorithm and its best variants on real computers, including how to apply various code optimization techniques. A detailed implementation combining the most effective improvements to Quicksort is given, along with a discussion of how to implement it in assembly language. Analytic results describing the performance of the programs are summarized. A variety of special situations are considered from a practical standpoint to illustrate Quicksort's wide applicability as an internal sorting method which requires negligible extra storage.

References

1. 1 Boothroyd, J. Sort of a section of the elements of an array by determining the rank of each element: Algorithm 25; and Ordering the subscripts of an array section according to the magnitudes of the elements: Algorithm 26. Comptr. J. 10 (Nov. 1967), 308-310. (See notes by R.S. Scowen in Comptr. J. 12 (Nov. 1969), 408-409, and by A.D. Woodall in Comptr. J. 13 (Aug. 1970.)
2. 2 Brawn, B.S., Gustavson, F.G., and Mankin, E. Sorting in a paging environment. Comm. ACM 13, 8 (Aug. 1970), 483-494.
3. 3 Cocke, J., and Schwartz, J.T. Programming languages and their compilers. Preliminary Notes. Courant Inst. of Math. Sciences, New York U., New York, 1970.
4. 4 Frazer, W.D., and McKellar, A.C. Samplesort: A sampling approach to minimal storage tree sorting. J. ACM 17, 3 (July 1970), 496-507.
5. 5 Hoare, C.A.R. Partition: Algorithm 63; Quicksort: Algorithm 64; and Find: Algorithm 65. Comm. ACM 4, 7 (July 1961), 321-322. (See also certification by J.S. Hillmore in Comm. ACM 5, 8 (Aug. 1962), 439, and B. Randell and L.J. Russell in Comm. A CM 6, 8 (Aug. 1963), 446.)
6. 6 Hoare, C.A.R. Quicksort. Computer J. 5, 4 (April 1962), 10-15.
7. 7 Knuth, D.E. The Art of Computer Programming, VoL 1: Fundamental Algorithms. Addison-Wesley, Mass., 1968.
8. 8 Knuth, D.E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, Mass., 1969.
9. 9 Knuth, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Mass., 1972.
10. 10 Knuth, D.E. Structured programming with go to statements. Computing Surveys 6, 4 (Dec. 1974), 261-301.
11. 11 Loeser, R. Some performance tests of "quicksort" and descendants. Comm. ACM 17, 3 (March 1974), 143-152.
12. 12 Morris, R. Some theorems on sorting. SlAM J. Appl. Math. 17, 1 (Jan. 1969), I-6.
13. 13 Rich, R.P. Internal Sorting Methods Illustrated with PL/I Progams. Prentice-Hall, Englewood Cliffs, N.J., 1972.
14. 14 Scowen, R.S. Quickersort: Algorithm 271. Comm. ACM 8, 11 (Nov. 1965), 669-670. (See also certification by C.R. Blair in Comm. ACM 9, 5 (May 1966), 354.)
15. 15 Sedgewick, R. Quicksort. Ph.D. Th. Stanford Comptr. Sci. Rep. STAN-CS-75-492, Stanford U., Stanford, Calif., May 1975.
16. 16 Sedgewick, R. Quicksort with equal keys. Siam J. Comput. 6, 2 (June 1977), 240-287.
17. 17 Sedgewick, R. The analysis of Quicksort programs. Acta Informatica 7 (1977), 327-355.
18. 18 Singleton, R.C. An efficient algorithm for sorting with minimal storage: Algorithm 347. Comm. ACM 12, 3 (March 1969), 185-187. (See also remarks by R. Griffin and K.A. Redish in Comm. ACM 13, l (Jan. 1970), 54 and by R. Peto, Comm. ACM 13, l0 (Oct. 1970), 624.)
19. 19 Stone, H.S. Sorting on STAR. IEEE Trans. Software Eng. SE-4, 2 (Mar. 1978), 138-146.
20. 20 van Emaen, M.N. Increasing the efficiency of quicksort: Algorithm 402. Comm. ACM 13, 11 (Nov. 1970), 693-694. (See also the article by the same name in Comm. ACM 13, 9 (Sept. 1970), 563-567.)
21. 21 Wirth, N. Algorithms + Data Structures = Programs. Prentice- Hall, Englewood Cliffs, N.J., 1976.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching