Algorithms in a Nutshell

(^102) | Chapter 4: Sorting Algorithms
Double Benchmark Results
The benchmarks using double floating-point values (Tables 4-12 through 4-16)
eliminate much of the overhead that was simply associated with string compari-
sons. Once again, we omit INSERTIONSORTand SELECTIONSORTfrom these
tables.
65,536 0.0151 0.024 0.0374 0.0505 0.0979
131,072 0.0333 0.0618 0.0816 0.1126 0.2257
Table 4-12. Performance (in seconds) on random floating-point values
n Bucket Sort
Quicksort
median-of-
three Median Sort Heap Sort
Quicksort
BFPRT^4
minSize=4
4,096 0.0009 0.0009 0.0017 0.0012 0.0003
8,192 0.0017 0.002 0.0039 0.0029 0.0069
16,384 0.0041 0.0043 0.0084 0.0065 0.0157
32,768 0.0101 0.0106 0.0196 0.0173 0.039
65,536 0.0247 0.0268 0.0512 0.0527 0.1019
131,072 0.0543 0.0678 0.1354 0.1477 0.26623
Table 4-13. Performance (in seconds) on ordered floating-point values
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.0052 0.0067 0.0055 0.0089
32,768 0.0073 0.0127 0.015 0.0133 0.0208
65,536 0.0145 0.0299 0.0336 0.0306 0.0483
131,072 0.0291 0.065 0.0737 0.0823 0.1113
Table 4-14. Performance (in seconds) on killer median data
n Bucket Sort Heap Sort Median Sort
Quicksort
median-of-
three
Quicksort
BFPRT^4
minSize=4
4,096 0.0008 0.0011 0.0015 0.0015 0.0025
8,192 0.0016 0.0024 0.0034 0.0033 0.0056
16,384 0.0035 0.0053 0.0071 0.0076 0.0122
Table 4-11. Performance (in seconds) on n/4 random pairs of elements swapped four
locations away (continued)
n
Hash Sort
17,576 buckets
Quicksort
median-of-
three Heap Sort Median Sort
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