Implementing Quicksort programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementing Quicksort programs

Full text

Pdf (1.09 MB)

Source

Communications of the ACM archive
Volume 21 , Issue 10 (October 1978) table of contents

Pages: 847 - 857

Year of Publication: 1978

ISSN:0001-0782

Author

Robert Sedgewick

Brown Univ., Providence, RI

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 31, Downloads (12 Months): 225, Citation Count: 25

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359619.359631 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	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	Barbara S. Brawn , Frances G. Gustavson , Efrem S. Mankin, Sorting in a paging environment, Communications of the ACM, v.13 n.8, p.483-494, Aug. 1970 [doi>10.1145/362705.362710]
	3	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	4	W. D. Frazer , A. C. McKellar, Samplesort: A Sampling Approach to Minimal Storage Tree Sorting, Journal of the ACM (JACM), v.17 n.3, p.496-507, July 1970 [doi>10.1145/321592.321600]
	5	C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
	6	Hoare, C.A.R. Quicksort. Computer J. 5, 4 (April 1962), 10-15.
	7	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	8	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	9	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	10	Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
	11	Rudolf Loeser, Some performance tests of “quicksort” and descendants, Communications of the ACM, v.17 n.3, p.143-152, March 1974 [doi>10.1145/360860.360870]
	12	Morris, R. Some theorems on sorting. SlAM J. Appl. Math. 17, 1 (Jan. 1969), I-6.
	13	Rich, R.P. Internal Sorting Methods Illustrated with PL/I Progams. Prentice-Hall, Englewood Cliffs, N.J., 1972.
	14	Charles R. Blair, Certification of Algorithm 271: Quickersort, Communications of the ACM, v.9 n.5, p.354, May 1966 [doi>10.1145/355592.365613]
	15	Sedgewick, R. Quicksort. Ph.D. Th. Stanford Comptr. Sci. Rep. STAN-CS-75-492, Stanford U., Stanford, Calif., May 1975.
	16	Sedgewick, R. Quicksort with equal keys. Siam J. Comput. 6, 2 (June 1977), 240-287.
	17	Sedgewick, R. The analysis of Quicksort programs. Acta Informatica 7 (1977), 327-355.
	18	Richard C. Singleton, Algorithm 347: an efficient algorithm for sorting with minimal storage [M1], Communications of the ACM, v.12 n.3, p.185-186, March 1969 [doi>10.1145/362875.362901]
	19	Stone, H.S. Sorting on STAR. IEEE Trans. Software Eng. SE-4, 2 (Mar. 1978), 138-146.
	20	M. H. van Emden, Algorithms 402: Increasing the efficiency of quicksort, Communications of the ACM, v.13 n.11, p.693-694, Nov 1970 [doi>10.1145/362790.362803]
	21	Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

CITED BY 24

	Youran Lan , Magdi A. Mohamed, Parallel Quicksort in hypercubes, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.740-746, March 1992, Kansas City, Missouri, United States
	Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
	Roger L. Wainwright, Quicksort algorithms with an early exit for sorted subfiles, Proceedings of the 15th annual conference on Computer Science, p.183-190, February 1987, St. Louis, Missouri, United States
	Michael J. Quinn , Philip J. Hatcher , Karen C. Jourdenais, Compiling C* programs for a hypercube multicomputer, ACM SIGPLAN Notices, v.23 n.9, p.57-65, Sept. 1988
	Li Xiao , Xiaodong Zhang , Stefan A. Kubricht, Improving memory performance of sorting algorithms, Journal of Experimental Algorithmics (JEA), 5, p.3-es, 2000
	Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
	Jukka Teuhola , Lutz Wegner, Minimal space, average linear time duplicate deletion, Communications of the ACM, v.34 n.3, p.62-73, March 1991
	Jon Bentley, Programming pearls: how to sort, Communications of the ACM, v.27 n.4, p.287-ff., April 1984
	R. S. Francis , I. D. Mathieson, A Benchmark Parallel Sort for Shared Memory Multiprocessors, IEEE Transactions on Computers, v.37 n.12, p.1619-1626, December 1988
	John G. Lewis, Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King Algorithms, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.180-189, June 1982
	P. Heidelberger , A. Norton , John T. Robinson, Parallel Quicksort Using Fetch-And-Add, IEEE Transactions on Computers, v.39 n.1, p.133-138, January 1990
	Jesper Bojesen , Jyrki Katajainen , Maz Spork, Performance engineering case study: heap construction, Journal of Experimental Algorithmics (JEA), 5, p.15-es, 2000
	B. Abali , F. özgü , A. Bataineh, Balanced Parallel Sort on Hypercube Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.572-581, May 1993
	Joseph JaJa, A Perspective on Quicksort, Computing in Science and Engineering, v.2 n.1, p.43-49, January 2000
	Xiaoming Li , María Jesús Garzarán , David Padua, A Dynamically Tuned Sorting Library, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.111, March 20-24, 2004, Palo Alto, California
	Markus Hegland, Implementing partition on vector computers, Proceedings of the 5th international conference on Supercomputing, p.304-311, June 17-21, 1991, Cologne, West Germany
	Hansheng Wang, A note on iterative marginal optimization: a simple algorithm for maximum rank correlation estimation, Computational Statistics & Data Analysis, v.51 n.6, p.2803-2812, March, 2007
	Paul Biggar , Nicholas Nash , Kevin Williams , David Gregg, An experimental study of sorting and branch prediction, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Xiaoming Li , Maria Jesus Garzaran , David Padua, Optimizing Sorting with Genetic Algorithms, Proceedings of the international symposium on Code generation and optimization, p.99-110, March 20-23, 2005
	Sunny Y. Wang, A new sort algorithm: self-indexed sort, ACM SIGPLAN Notices, v.31 n.3, p.28-36, March 1996
	Jacinta Townley , Joseph Manning , Michel Schellekens, Sorting Algorithms in MOQA, Electronic Notes in Theoretical Computer Science (ENTCS), 225, p.391-404, January, 2009
	Xavier Teruel , Priya Unnikrishnan , Xavier Martorell , Eduard Ayguadé , Raul Silvera , Guansong Zhang , Ettore Tiotto, OpenMP tasks in IBM XL compilers, Proceedings of the 2008 conference of the center for advanced studies on collaborative research: meeting of minds, October 27-30, 2008, Ontario, Canada
	Gerth Stølting Brodal , Rolf Fagerberg , Gabriel Moruz, On the adaptiveness of Quicksort, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Eunsang Kim , Kunsoo Park, Improving multikey Quicksort for sorting strings with many equal elements, Information Processing Letters, v.109 n.9, p.454-459, April, 2009