Algorithms in a Nutshell

(^100) | Chapter 4: Sorting Algorithms
Sorted
The input elements can be presorted into ascending order (the ultimate goal)
or in descending order.
Killer median-of-three
Musser (1997) discovered an ordering that ensures that QUICKSORTrequires
O(n^2 ) comparisons when using median-of-three to choose a pivot.
Nearly sorted
Given a set of sorted data, we can selectkpairs of elements to swap and the
distancedwith which to swap (or 0 if any two pairs can be swapped). Using
this capability, you can construct input sets that might more closely match
your input set.
The upcoming tables are ordered left to right, based upon how well the algorithms
perform on the final row in the table. Each section has four tables, showing perfor-
mance results under the four different situations outlined earlier in this chapter.
String Benchmark Results
Because INSERTIONSORTand SELECTIONSORTare the two slowest algorithms in
this chapter on randomly uniform data (by several orders of magnitude) we omit
these algorithms from Tables 4-7 through 4-11. However, it is worth repeating that
on sorted data (Table 4-8) and nearly sorted data (Tables 4-10 and 4-11) INSERTION
SORTwill outperform the other algorithms, often by an order of magnitude. To
produce the results shown in Tables 4-7 through 4-11, we executed each trial 100
times on the high-end computer and discarded the best and worst performers. The
average of the remaining 98 trials is shown in these tables. The columns labeled
QUICKSORTBFPRT^4 MINSIZE=4 refer to a QUICKSORTimplementation that uses
BFPRT (with groups of 4) to select the partition value and which switches to INSER-
TIONSORT when a subarray to be sorted has four or fewer elements.
Table 4-7. Performance results (in seconds) on random 26-letter permutations of the alphabet
n
Hash Sort
17,576 buckets
Quicksort
median-of-
three Heap Sort Median Sort
Quicksort
BFPRT^4
minSize=4
4,096 0.0012 0.0011 0.0013 0.0023 0.0041
8,192 0.002 0.0024 0.0031 0.005 0.0096
16,384 0.0044 0.0056 0.0073 0.0112 0.022
32,768 0.0103 0.014 0.0218 0.0281 0.0556
65,536 0.0241 0.0342 0.0649 0.0708 0.1429
131,072 0.0534 0.0814 0.1748 0.1748 0.359
Table 4-8. Performance (in seconds) on ordered random 26-letter permutations of the
alphabet
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
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