Java Reference
In-Depth Information
11.
A
counting sort
is a simple way to sort an array of
n
positive integers that lie between 0 and
m
, inclusive. You need
m
+
1 counters. Then, making only one pass through the array, you count the number of times each integer occurs in
the array. For example, Figure 9-12 shows an array of integers that lie between 0 and 4 and the five counters after a
counting sort has made its pass through the array. From the counters, you can see that the array contains one 0, three
1s, two 2s, one 3, and three 4s. These counts enable you to determine that the sorted array should contain
0111223444.
a.
Write a method that performs a counting sort.
b.
How does the efficiency of a counting sort compare to that of an insertion sort or a quick sort?
FIGURE 9-12
A counting sort of an array (see Exercise 11)
Original array
4
2
1
3
4
1
2
1
0
4
One 0
Three 1s
Two 2s
One 3
Three 4s
1
0
3
2
2
1
3
4
Counters
1
3
Sorted array
0
1
1
1
2
2
3
4
4
4
P
ROJECTS
1.
Implement the recursive algorithm for merge sort.
2.
Segment 9.8 introduced you to an iterative merge sort. This project continues that discussion by providing more
details about the merge steps.
a.
If
n
is a power of 2, as it is in Figure 9-3, you would merge pairs of individual entries, starting at the
beginning of the array. Then you would return to the beginning of the array and merge pairs of two-
entry subarrays. Finally, you would merge one pair of four-entry subarrays. Notice that the subarrays
in each pair of subarrays contain the same number of entries.
In general,
n
might not be a power of 2. After merging a certain number of pairs of subarrays, you
might have too few entries left to make up a complete pair of subarrays. In Figure 9-13a, after merging
pairs of single entries, one entry is left over. You then merge one pair of two-entry subarrays, and merge
the leftover two-entry subarray with the leftover single entry. Parts
b
and
c
of Figure 9-13 show two
other possibilities.
Implement an iterative merge sort. Use the algorithm
merge
that was given in Segment 9.3. A private
method that uses
merge
to merge the pairs of subarrays is useful. After the method completes its task, you
can handle the leftovers that we just described.
b.
Merging two subarrays requires an additional temporary array. Although you need to use this extra
space, you can save much of the time that our earlier merge algorithm spends in copying entries
from the temporary array back to the original array. If
a
is the original array and
t
is the temporary
array, you first merge subarrays of
a
into the array
t
. Instead of copying
t
back to
a
and continuing
the merge, you determine subarrays of
t
and merge them into
a
. If you can do this an even number
of times, no additional copying is necessary. Make these changes to the iterative merge sort that
you wrote in Part
a
.
