Rudolf Loeser
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.
- 1 Hoare, C.A.R. Algorithm 64, quicksort. Comm. ACM 4, 7 (July 1961), p. 321. Google Scholar
Digital Library
- 2 Boothroyd J. Algorithm 201, Shellsort. Comm. ACM 6, 8 (Aug. 1963), p. 445.Google Scholar
- 3 Boothroyd, J. Algorithm 207, stringsort. Comm. ACM 6, 10 (Oct. 1963), p. 615. Google ScholarDigital Library
- 4 Floyd, R.W. Algorithm 245, TREESORT3. Comm. ACM 7, 12 (Dec. 1964), p. 701. Google ScholarDigital Library
- 5 Scowen, R.S. Algorithm 271, quickersort. Comm. ACM 8, 11 (Nov. 1965), 669-670. Google ScholarDigital Library
- 6 van Emden, M.H. Algorithm 402, qsort. Comm. ACM 13, 11 (Nov. 1970), 693-694. Google ScholarDigital Library
- 7 Hoare, C.A.R. Quicksort. Comp. J. 5 (1962), 10-15.Google ScholarCross Ref
- 8 Foley, M., and Hoare, C.A.R. Proof of a rccursive program: Quicksort. Comp. J. 14, 4 (Nov. 1971), 391-395.Google ScholarCross Ref
- 9 Hillmore, J.S. Certification of Algorithms 63, 64, 65. Comm. ACM5, 8 (Aug. 1962), p. 439. Google ScholarDigital Library
- 10 van Emden, M.H. Increasing the efficiency of quicksort. Comm. ACM 13, 9 (Sept. 1970), 563-567. Google ScholarDigital Library
- 11 Frazer, W.D., and McKellar, A.C. Samplesort: A sampling approach to minimal storage tree sorting. J. ACM 17, 3 (July 1970), 496-507. Google ScholarDigital Library
- 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.).Google Scholar
- 13 Pike, M.C., and Hill, I.D. Algorithm 266, random. Comm. ACM 8, 10 (Oct. 1965), 605-606. (Use d here with y = 62104023.) Google ScholarDigital Library
- 14 Control Data Corporation 6000 Series Algol, Version 2 (Scope Level 3.3).Google Scholar
- 15 Blair, C.R. Certification of Algorithm 271. Comm. ACM 9, 5 (May 1966), p. 354. Google ScholarDigital Library
- 16 Abrams, P.S. Certification of Algorithm 245. Comm. ACM 8, 7 (July 1965), p. 445. Google ScholarDigital Library
- 17 London, R.L. Certification of Algorithm 245. Comm. ACM 13, 6 (June 1970), 371-373. Google ScholarDigital Library
Index Terms
- Some performance tests of “quicksort” and descendants
Recommendations
GPU-Quicksort: A practical Quicksort algorithm for graphics processors
In this article, we describe GPU-Quicksort, an efficient Quicksort algorithm suitable for highly parallel multicore graphics processors. Quicksort has previously been considered an inefficient sorting solution for graphics processors, but we show that ...
Best sorting algorithm for nearly sorted lists
Straight Insertion Sort, Shellsort, Straight Merge Sort, Quickersort, and Heapsort are compared on nearly sorted lists. The ratio of the minimum number of list elements which must be removed so that the remaining portion of the list is in order to the size ...
Optimal Partitioning for Dual-Pivot Quicksort
Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot ...
Comments