Java Reference
In-Depth Information
4.
Revise the implementation of quick sort as follows. If the array has 7 entries, choose the middle entry as the pivot.
For arrays of between 8 and 40 entries, use the median-of-three pivot-selection scheme described in Segments 9.14
and 9.16. For larger arrays, the pivot is the median of 9 entries that are about equally spaced, including the first, last,
and middle entries. For arrays of fewer than 7 entries, use insertion sort instead of quick sort.
5.
Extend Project 1 of the previous chapter to provide graphical demonstrations of the merge sort and quick sort
algorithms introduced in this chapter.
6.
The
median
of a collection of data is the middle value. One way to find the median is to sort the data and take the
value that is at—or nearly at—the center of the collection. But sorting does more than necessary to find the median.
You need to find only the
k
th
smallest entry in the collection for an appropriate value of
k
. To find the median of
n
items, you would take
k
as
n
/
2 rounded up—that is, .
You can use the partitioning strategy of quick sort to find the
k
th
smallest entry in an array. After choosing a
pivot and forming the subarrays
Smaller
and
Larger
, as described in Segment 9.10, you can draw one of the fol-
lowing conclusions:
n
⁄
2
If
Smaller
contains
k
or more entries, it must contain the
k
th
smallest entry.
•
If
Smaller
contains
k
-
1 entries, the
k
th
smallest entry is the pivot.
•
If
Smaller
contains fewer than
k
-
1 entries, the
k
th
smallest entry is in
Larger
.
You now can develop a recursive solution to finding the
k
th
smallest entry. The first and last conclusions corre-
spond to the recursive calls. The remaining one is the base case.
Implement a recursive method that finds the
k
th
smallest entry in an unsorted array. Use your method to find
the median in the array.
•
7.
A binary radix sort will sort an array
a
of
n
integer values based on their binary bits instead of their decimal digits.
This sort will need only two buckets. Represent the buckets as a 2 by
n
array. You can avoid some work by not
copying the contents of the buckets back into the array
a
at the end of each pass. Instead just add the values from
the second bucket to the end of the first bucket.
Implement this algorithm.
8.
Repeat Project 3 of the previous chapter, but instead compare the merge sort and the quick sort.
9.
Implement a merge sort of the objects in a chain of linked nodes. Compare the run times of this version of merge
sort and a quick sort of the same data in an array. See the projects at the end of Chapter 4 for a description of how
to time a block of Java code.
10.
Implement a radix sort of the strings in a chain of linked nodes.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
96248753
9624 8753
96 24 87 53
96 24 87 53
69 24 78 35
2469 3578
23456789
