Java Reference
In-Depth Information
PROGRAMMING EXERCISES
Exercise P14.1. Modify the selection sort algorithm to sort an array of
integers in descending order.
Exercise P14.2. Modify the selection sort algorithm to sort an array of
coins by their value.
661
662
Exercise P14.3. Write a program that generates the table of sample runs of
the selection sort times automatically. The program should ask for the
smallest and largest value of
n
and the number of measurements and then
make all sample runs.
Exercise P14.4. Modify the merge sort algorithm to sort an array of strings
in lexicographic order.
Exercise P14.5. Write a telephone lookup program. Read a data set of
1,000 names and telephone numbers from a file that contains the
numbers in random order. Handle lookups by name and also reverse
lookups by phone number. Use a binary search for both lookups.
Exercise P14.6. Implement a program that measures the performance of
the insertion sort algorithm described in Advanced Topic 14.1.
Exercise P14.7. Write a program that sorts an
ArrayList<Coin>
in
decreasing order so that the most valuable coin is at the beginning of the
array. Use a
Comparator
.
Exercise P14.8. Consider the binary search algorithm in
Section 14.7
. If
no match is found, the
search
method returnsɨ1. Modify the method so
that if a is not found, the method returnsɨkɨ1, where k is the position
before which the element should be inserted. (This is the same behavior as
Arrays.binarySearch
.)
Exercise P14.9. Implement the
sort
method of the merge sort algorithm
without recursion, where the length of the array is a power of 2. First
merge adjacent regions of size 1, then adjacent regions of size 2, then
adjacent regions of size 4, and so on.