Algorithms in a Nutshell

Criteria for Choosing a Sorting Algorithm | 101

Sorting

Algorithms

16,384 0.0037 0.0036 0.0062 0.0094 0.0161

32,768 0.0074 0.0082 0.0157 0.0216 0.0381

65,536 0.0161 0.0184 0.0369 0.049 0.0873

131,072 0.0348 0.0406 0.0809 0.1105 0.2001

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

n

Hash Sort

17,576 buckets Heap Sort Median Sort

Quicksort

BFPRT^4

minSize=4

Quicksort

median-of-

threea

aBecause the performance of QUICKSORTmedian-of-three degrades so quickly, only 10 trials were executed; the table shows the average of

eight runs once the best and worst performers were discarded.

4,096 0.0011 0.0012 0.0021 0.0039 0.0473

8,192 0.0019 0.0028 0.0045 0.0087 0.1993

16,384 0.0038 0.0066 0.0101 0.0194 0.8542

32,768 0.0077 0.0179 0.024 0.0472 4.083

65,536 0.0171 0.0439 0.056 0.1127 17.1604

131,072 0.038 0.1004 0.1292 0.2646 77.4519

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

locations away

n

Hash Sort

17,576 buckets

Quicksort

median-of-

three Heap Sort Median Sort

Quicksort

BFPRT^4

minSize=4

4,096 0.0011 0.0007 0.0012 0.002 0.0031

8,192 0.0019 0.0015 0.0027 0.0042 0.007

16,384 0.0038 0.0035 0.0063 0.0094 0.0161

32,768 0.0072 0.0081 0.0155 0.0216 0.038

65,536 0.0151 0.0182 0.0364 0.0491 0.0871

131,072 0.0332 0.0402 0.08 0.1108 0.2015

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

locations away

n

Hash Sort

17,576 buckets

Quicksort

median-of-

three Heap Sort Median Sort

Quicksort

BFPRT^4

minSize=4

4,096 0.0011 0.0008 0.0012 0.002 0.0035

8,192 0.0019 0.0019 0.0028 0.0044 0.0078

16,384 0.0039 0.0044 0.0064 0.0096 0.0175

32,768 0.0073 0.01 0.0162 0.0221 0.0417

Table 4-8. Performance (in seconds) on ordered random 26-letter permutations of the alphabet

(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