Algorithms in a Nutshell

(^90) | Chapter 4: Sorting Algorithms
HEAPSORTsucceeds because of theheapifyfunction. It is used in two distinct
places, although it serves the same purpose each time.
Analysis
heapifyis the central operation in HEAPSORT.InbuildHeap, it is called⎣n/2⎦–1
times, and during the actual sort it is calledn–1 times, for a total of⎣3n/2⎦–2 times.
As you can see, it is a recursive operation that executes a fixed number of computa-
tions until the end of the heap is reached. Because of the shape property, the
depth of the heap will always be⎣logn⎦, wherenis the number of elements in the
heap. The resulting performance, therefore, is bounded by (⎣3n/2⎦–2)*⎣logn⎦,
which is O(n logn).
Variations
Non-recursive HEAPSORTimplementations are available, and Table 4-4 presents
a benchmark comparison on running 1,000 randomized trials of both implemen-
tations, discarding the best and worst performances of each. The average of the
remaining runs is shown for both implementations.
ar[idx] = ar[largest];
ar[largest] = tmp;
heapify(ar, cmp, largest, max);
}
}
static void buildHeap (void *ar,
int(cmp)(const void ,const void ), int n) {
int i;
for (i = n/2-1; i>=0; i--) {
heapify (ar, cmp, i, n);
}
}
void sortPointers (void *ar, int n,
int(cmp)(const void ,const void )) {
int i;
buildHeap (ar, cmp, n);
for (i = n-1; i >= 1; i--) {
void *tmp;
tmp = ar[0];
ar[0] = ar[i];
ar[i] = tmp;
heapify (ar, cmp, 0, i);
}
}
Example 4-9. Heap Sort implementation in C (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