Java Reference
In-Depth Information
4.
Consider an
n
by
n
array of integer values.
a.
Write an algorithm to sort the rows of the array by their first value.
b.
Using Big Oh notation, describe the efficiency of your algorithm.
c.
Implement your algorithm.
5.
Suppose that you want to perform a Shell sort on a linked chain.
a.
Revise the method
incrementalInsertionSort
to work with a linked chain instead of an array.
b.
Compare the performance of
incrementalInsertionSort
on an array with its performance on a linked chain.
c.
Using the revised method, implement a Shell sort for a linked chain.
d.
Find the run time required to sort
n
values in a linked chain for different values of
n
. (See the projects at
the end of Chapter 4 for a description of how to time a block of Java code.) Graph the run time versus
n
.
e.
Assuming that the performance of your sort is O(
n
k
), make an estimate for the value of
k
.
6.
You can sort a large array of integers that are in the range 1 to
n
by using an array
count
of
n
entries to count the
number of occurrences of each integer in the array. For example, consider the following array of 14 integers that
range from 1 to 9:
9 2 4 8 9 4 3 2 8 1 2 7 2 5
Form an array
count
of 9 elements such that
count[i- 1]
contains the number of times that
i
occurs in the array
to be sorted. Thus,
count
is
1 4 1 2 1 0 1 2 2
We now know that 1 occurs once in the original array, 2 occurs four times, and so on. Thus, the sorted array is
1 2 2 2 2 3 4 4 5 7 8 8 9 9
a.
Implement this sorting algorithm.
b.
Using Big Oh notation, describe the efficiency of this algorithm.
c.
Is this algorithm useful as a general sorting algorithm? Explain.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
96248
26948
24968
24698
24689
2.
96248
69248
26948
24698
24689
3.
No;
insertInOrder
links the node to be inserted into the sorted part of the chain so that the node no longer refer-
ences the rest of the unsorted part. Since
unsortedPart
still references the inserted node, executing the line in
question next would make
unsortedPart
either reference a node in the sorted part or be
null
.
4.
The public method
insertionSort
is to be invoked by using an object of
LinkedGroup
, which is the class that
defines this method. Thus, the method should not be static.
