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