Selection Sort | 85SortingAlgorithmssubarrays only, and use INSERTION SORT for small ones, as shown in
Example 4-7.
Sedgewick (1978) suggests that a combination of median-of-three and using
INSERTIONSORTfor small subarrays offers a speedup of 20–25% over pure
QUICKSORT.IntroSortSwitching to INSERTIONSORTfor small subarrays is a local decision that is made
based upon the size of the subarray. Musser (1997) introduced a QUICKSORT
variation called INTROSORT, which monitors the recursive depth of QUICKSORT
to ensure efficient processing. If the depth of the QUICKSORTrecursion exceeds
log (n) levels, then INTROSORTswitches to HEAPSORT. The SGI implementa-
tion of the C++ Standard Template Library uses INTROSORTas its default sorting
mechanism (http://www.sgi.com/tech/stl/sort.html).Selection Sort
Given a pile of cards with numbers on them, a common way to sort the pile is to
select and remove the largest card, and then repeat the process until all cards are
gone. This approach describes SELECTIONSORT, which sorts in place the
elements inA[0,n), as shown in Example 4-8.Example 4-8. Selection Sort implementation in C
static int selectMax (void **ar, int left, int right,
int (*cmp)(const void *,const void *)) {
int maxPos = left;
int i = left;
while (++i <= right) {
if (cmp(ar[i], ar[maxPos])> 0) {
maxPos = i;
}
}return maxPos;
}void sortPointers (void **ar, int n,
int(*cmp)(const void *,const void *)) {
int i;/* repeatedly select max in A[0,i] and swap with proper position */
for (i = n-1; i >=1; i--) {
int maxPos = selectMax (ar, 0, i, cmp);
if (maxPos != i) {
void *tmp = ar[i];
ar[i] = ar[maxPos];
ar[maxPos] = tmp;
}
}
}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