Java Reference
In-Depth Information
19.3
In what sense is the insertion sort superior to the merge sort? In what sense is the merge sort
superior to the insertion sort?
19.4
In the text, we say that after the merge sort splits the array into two subarrays, it then sorts
these two subarrays and merges them. Why might someone be puzzled by our statement that “it
then sorts these two subarrays”?
Answers to Self-Review Exercises
19.1
a) 16, because an
O
(
n
2
) algorithm takes 16 times as long to sort four times as much infor-
mation. b)
O
(
n
log
n
).
19.2
Both of these algorithms incorporate “halving”—somehow reducing something by half.
The binary search eliminates from consideration one-half of the array after each comparison. The
merge sort splits the array in half each time it's called.
19.3
The insertion sort is easier to understand and to program than the merge sort. The merge
sort is far more efficient [
O
(
n
log
n
)] than the insertion sort [
O
(
n
2
)].
19.4
In a sense, it does not really sort these two subarrays. It simply keeps splitting the original
array in half until it provides a one-element subarray, which is, of course, sorted. It then builds up
the original two subarrays by merging these one-element arrays to form larger subarrays, which are
then merged, and so on.
Exercises
19.5
(Bubble Sort)
Implement bubble sort—another simple yet inefficient sorting technique. It's
called bubble sort or sinking sort because smaller values gradually “bubble” their way to the top of
the array (i.e., toward the first element) like air bubbles rising in water, while the larger values sink
to the bottom (end) of the array. The technique uses nested loops to make several passes through
the array. Each pass compares successive pairs of elements. If a pair is in increasing order (or the
values are equal), the bubble sort leaves the values as they are. If a pair is in decreasing order, the
bubble sort swaps their values in the array. The first pass compares the first two elements of the array
and swaps their values if necessary. It then compares the second and third elements in the array. The
end of this pass compares the last two elements in the array and swaps them if necessary. After one
pass, the largest element will be in the last index. After two passes, the largest two elements will be
in the last two indices. Explain why bubble sort is an
O
(
n
2
) algorithm.
19.6
(Enhanced Bubble Sort)
Make the following simple modifications to improve the perfor-
mance of the bubble sort you developed in Exercise 19.5:
a) After the first pass, the largest number is guaranteed to be in the highest-numbered array
element; after the second pass, the two highest numbers are “in place”; and so on. In-
stead of making nine comparisons on every pass for a ten-element array, modify the
bubble sort to make eight comparisons on the second pass, seven on the third pass, and
so on.
b) The data in the array may already be in proper or near-proper order, so why make nine
passes if fewer will suffice? Modify the sort to check at the end of each pass whether any
swaps have been made. If there were none, the data must already be sorted, so the pro-
gram should terminate. If swaps have been made, at least one more pass is needed.
19.7
(Bucket Sort)
A bucket sort begins with a one-dimensional array of positive integers to be
sorted and a two-dimensional array of integers with rows indexed from 0 to 9 and columns indexed
from 0 to
n
- 1, where
n
is the number of values to be sorted. Each row of the two-dimensional array
