Algorithms in a Nutshell

References | 103

Sorting

Algorithms

References

Bentley, Jon Louis and M. Douglas McIlroy, “Engineering a Sort Function,”

Software—Practice and Experience, 23(11): 1249–1265, 1993, http://citeseer.ist.

psu.edu/bentley93engineering.html.

Blum, Manuel, Robert Floyd, Vaughan Pratt, Ronald Rivest, and Robert Tarjan,

“Time bounds for selection.”Journal of Computer and System Sciences, 7(4):

448–461, 1973.

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,

Introduction to Algorithms, Second Edition. McGraw-Hill, 2001.

32,768 0.0079 0.0134 0.0164 0.0192 0.0286

65,536 0.0157 0.0356 0.0376 0.0527 0.0686

131,072 0.0315 0.0816 0.0854 0.1281 0.1599

Table 4-15. Performance (in seconds) on 16 random pairs of elements swapped eight

locations away

n Bucket Sort Heap Sort Median Sort

Quicksort

median-of-

three

Quicksort

BFPRT^4

minSize=4

4,096 0.0007 0.0011 0.0015 0.0012 0.0018

8,192 0.0015 0.0024 0.0032 0.0025 0.004

16,384 0.0035 0.0051 0.0067 0.0054 0.0089

32,768 0.0071 0.0127 0.0151 0.0133 0.0209

65,536 0.0142 0.0299 0.0336 0.0306 0.0482

131,072 0.0284 0.065 0.0744 0.0825 0.111

Table 4-16. Performance (in seconds) on n/4 random pairs of elements swapped four

locations away

n Bucket Sort Heap Sort

Quicksort

median-of-

three Median Sort

Quicksort

BFPRT^4

minSize=4

4,096 0.0001 0.0014 0.0015 0.0019 0.005

8,192 0.0022 0.0035 0.0032 0.0052 0.012

16,384 0.0056 0.0083 0.0079 0.0099 0.0264

32,768 0.0118 0.0189 0.0189 0.0248 0.0593

65,536 0.0238 0.0476 0.045 0.0534 0.129

131,072 0.0464 0.1038 0.1065 0.1152 0.2754

Table 4-14. Performance (in seconds) on killer median data (continued)

n Bucket Sort Heap Sort Median Sort

Quicksort

median-of-

three

Quicksort

BFPRT^4

minSize=4

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use