Java Reference
In-Depth Information
7.6 It has been proposed that Heapsort can be optimized by altering the heap's
siftdown function. Call the value being sifted down X. Siftdown does two
comparisons per level: First the children of X are compared, then the winner
is compared to X. If X is too small, it is swapped with its larger child and the
process repeated. The proposed optimization dispenses with the test against
X. Instead, the larger child automatically replaces X, until X reaches the
bottom level of the heap. At this point, X might be too large to remain in
that position. This is corrected by repeatedly comparing X with its parent
and swapping as necessary to “bubble” it up to its proper level. The claim
is that this process will save a number of comparisons because most nodes
when sifted down end up near the bottom of the tree anyway. Implement both
versions of siftdown, and do an empirical study to compare their running
times.
7.7 Radix Sort is typically implemented to support only a radix that is a power
of two. This allows for a direct conversion from the radix to some number
of bits in an integer key value. For example, if the radix is 16, then a 32-bit
key will be processed in 8 steps of 4 bits each. This can lead to a more effi-
cient implementation because bit shifting can replace the division operations
shown in the implementation of Section 7.7. Re-implement the Radix Sort
code given in Section 7.7 to use bit shifting in place of division. Compare
the running time of the old and new Radix Sort implementations.
7.8 Write your own collection of sorting programs to implement the algorithms
described in this chapter, and compare their running times. Be sure to im-
plement optimized versions, trying to make each program as fast as possible.
Do you get the same relative timings as shown in Figure 7.20? If not, why do
you think this happened? How do your results compare with those of your
classmates? What does this say about the difficulty of doing empirical timing
studies?
