Java Reference
In-Depth Information
subarray, only the subarray bounds. Furthermore, the stack depth can be kept small
if care is taken on the order in which Quicksort's recursive calls are executed. We
can also place the code for
findpivot
and
partition
inline to eliminate the
remaining function calls. Note however that by not processing sublists of size nine
or less as suggested above, about three quarters of the function calls will already
have been eliminated.
Thus, eliminating the remaining function calls will yield
only a modest speedup.
7.6
Heapsort
Our discussion of Quicksort began by considering the practicality of using a binary
search tree for sorting. The BST requires more space than the other sorting meth-
ods and will be slower than Quicksort or Mergesort due to the relative expense of
inserting values into the tree. There is also the possibility that the BST might be un-
balanced, leading to a (n
2
) worst-case running time. Subtree balance in the BST
is closely related to Quicksort's partition step. Quicksort's pivot serves roughly the
same purpose as the BST root value in that the left partition (subtree) stores val-
ues less than the pivot (root) value, while the right partition (subtree) stores values
greater than or equal to the pivot (root).
A good sorting algorithm can be devised based on a tree structure more suited
to the purpose. In particular, we would like the tree to be balanced, space efficient,
and fast. The algorithm should take advantage of the fact that sorting is a special-
purpose application in that all of the values to be stored are available at the start.
This means that we do not necessarily need to insert one value at a time into the
tree structure.
Heapsort is based on the heap data structure presented in Section 5.5. Heapsort
has all of the advantages just listed. The complete binary tree is balanced, its array
representation is space efficient, and we can load all values into the tree at once,
taking advantage of the efficient
buildheap
function. The asymptotic perfor-
mance of Heapsort is (n log n) in the best, average, and worst cases. It is not as
fast as Quicksort in the average case (by a constant factor), but Heapsort has special
properties that will make it particularly useful when sorting data sets too large to fit
in main memory, as discussed in Chapter 8.
A sorting algorithm based on max-heaps is quite straightforward. First we use
the heap building algorithm of Section 5.5 to convert the array into max-heap order.
Then we repeatedly remove the maximum value from the heap, restoring the heap
property each time that we do so, until the heap is empty. Note that each time
we remove the maximum element from the heap, it is placed at the end of the
array. Assume the n elements are stored in array positions 0 through n 1. After
removing the maximum value from the heap and readjusting, the maximum value
will now be placed in position n1 of the array. The heap is now considered to be
