Some performance tests of “quicksort” and descendants

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some performance tests of “quicksort” and descendants

Full text

Pdf (1.36 MB)

Source

Communications of the ACM archive
Volume 17 , Issue 3 (March 1974) table of contents

Pages: 143 - 152

Year of Publication: 1974

ISSN:0001-0782

Author

Rudolf Loeser

Smithsonian Insitution, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 38, Citation Count: 8

Additional Information:

abstract references cited by index terms

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/360860.360870 What is a DOI?

ABSTRACT

Detailed performance evaluations are presented for six ACM algorithms: quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), “TREESORT3” (No. 245), quickersort (No. 271), and qsort (No. 402). Algorithms 271 and 402 are refinements of algorithm 64, and all three are discussed in some detail. The evidence given here demonstrates that qsort (No. 402) requires many more comparisons than its author claims. Of all these algorithms, quickersort requires the fewest comparisons to sort random arrays.

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	C. A. R. Hoare, Algorithm 64: Quicksort, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366644]
	2	Boothroyd J. Algorithm 201, Shellsort. Comm. ACM 6, 8 (Aug. 1963), p. 445.
	3	J. Boothroyd, Algorithm 207: stringsort, Communications of the ACM, v.6 n.10, p.615, Oct. 1963 [doi>10.1145/367651.367662]
	4	Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
	5	R. S. Scowen, Algorithm 271: quickersort, Communications of the ACM, v.8 n.11, p.669-670, Nov. 1965 [doi>10.1145/365660.365678]
	6	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]
	7	Hoare, C.A.R. Quicksort. Comp. J. 5 (1962), 10-15.
	8	Foley, M., and Hoare, C.A.R. Proof of a rccursive program: Quicksort. Comp. J. 14, 4 (Nov. 1971), 391-395.
	9	J. S. Hillmore, Certification of Algorithms 63, 64, 65: Partition, quicksort, find, Communications of the ACM, v.5 n.8, p.439, Aug. 1962 [doi>10.1145/368637.368709]
	10	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]
	11	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]
	12	Murphy, H.M., Jr. RANF (random number generator for Control Data 6000 computers, written 22 Nov. 1968 at Air Force Weapons Laboratory, N.M.).
	13	M. C. Pike , I. D. Hill, Algorithm 266: pseudo-random numbers [G5], Communications of the ACM, v.8 n.10, p.605-606, Oct. 1965 [doi>10.1145/365628.365648]
	14	Control Data Corporation 6000 Series Algol, Version 2 (Scope Level 3.3).
	15	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]
	16	Philip S. Abrams, Certification of algorithm 245 [M1]: TREESORT, Communications of the ACM, v.8 n.7, p.445, July 1965 [doi>10.1145/364995.365687]
	17	Ralph L. London, Certification of algorithm 245 [M1]:treesort 3:proof of algorithms—a new kind of certification, Communications of the ACM, v.13 n.6, p.371-373, June 1970 [doi>10.1145/362384.362507]

CITED BY 8

	Roger L. Wainwright, A class of sorting algorithms based on Quicksort, Communications of the ACM, v.28 n.4, p.396-402, April 1985
	Jair M. Babad , V. Balachandran , Edward A. Stohr, Cost evaluation of storage schemes, Proceedings of the 1974 annual conference, p.54-60, January 1974
	Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980
	J. C. Browne, A critical overview of computer performance evaluation, Proceedings of the 2nd international conference on Software engineering, p.138-145, October 13-15, 1976, San Francisco, California, United States
	Robert Sedgewick, Implementing Quicksort programs, Communications of the ACM, v.21 n.10, p.847-857, Oct. 1978
	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
	Dalia Motzkin, Pracniques: Meansort, Communications of the ACM, v.26 n.4, p.250-251, April 1983
	Rudolf Loeser, Survey on Algorithms 347, 426, and Quicksort, ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.290-299, Sept. 1976