(^66) | Chapter 4: Sorting Algorithms
Consequences
Given the example in Figure 4-7, INSERTIONSORTneeded to transpose 60
elements that were already in sorted order. Since there were 15 passes made over
the array, on average four elements were moved during each pass. The optimal
performance occurs when the array is already sorted, and arrays sorted in reverse
order naturally produce the worst performance for INSERTIONSORT. If the array
is already “mostly sorted,” INSERTIONSORTdoes well because there is less need
to transpose the elements.
Analysis
In the best case, each of thenitems is in its proper place and thus INSERTION
SORTtakes linear time, or O(n). This may seem to be a trivial point to raise (how
often are you going to sort a set of already sorted elements?), but it is important
because INSERTIONSORTis the only sorting algorithm based on comparisons
discussed in this chapter that has this behavior.
Much real-world data is already “partially sorted,” so optimism and realism might
coincide to make INSERTIONSORTan effective algorithm for much real-world
data. But sadly, if every input permutation is equally likely, then the probability of
having optimal data (every item being in its proper position) is only 1/n!; for
n=10, the odds are already 3.6 million to one. Note that the efficiency of INSER-
TIONSORTincreases when duplicate items are present, since there are fewer
swaps to perform.
Unfortunately, INSERTIONSORTsuffers from being too conservative for “random
data.” If allnitems are distinct and the array is “random” (all permutations of the
data are equally likely), then each item starts on averagen/3 positions in the array
from its final resting place.So in the average case and worst case, each of then
items must be transposed a linear number of positions, and INSERTIONSORTwill
take quadratic time, or O(n^2 ).
INSERTIONSORToperates inefficiently for value-based data because of the
amount of memory that must be shifted to make room for a new value.
/ If already in place, no movement needed. Otherwise save value to be
- inserted and move as a LARGE block intervening values. Then insert
- into proper position. /
if (++i == j) continue;
memmove (saved, value, s);
memmove (base+(i+1)s, base+is, s(j-i));
memmove (base+i*s, saved, s);
}
free (saved);
} - The programnumTranspositionsin the code repository empirically validates this claim for small
n up to 12; also see Trivedi (2001).
Example 4-2. Insertion Sort using value-based information (continued)
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