Java Reference
In-Depth Information
•
Radix sort treats array entries as if they were strings that have the same length. Initially radix sort distributes
the entries into buckets according to the character (digit) at one end of the strings. The sort then collects the
strings and distributes them again among the buckets according to the character or digit in the next position.
The sort continues this process until all character positions are considered.
•
Radix sort does not compare array entries. Although it is O(
n
), it cannot sort all types of data. Thus, it is not
appropriate as a general-purpose sorting algorithm.
E
XERCISES
1.
Suppose that 80 90 70 85 60 40 50 95 represents an array of
Integer
objects. Show the steps that a merge
sort takes when sorting this array.
2.
Consider the method
quickSort
, as given in Segment 9.18, that sorts an array of objects into ascending order by
using a quick sort. Suppose that 80 90 70 85 60 40 50 95 represents an array of
Integer
objects.
a.
What does the array look like after
quickSort
partitions it for the first time? (Show all intermediate results.)
b.
How many comparisons did this partition process require?
c.
The pivot is now between two subarrays called
Smaller
and
Larger
. Will the position of this particular
entry change during subsequent steps of the sort? Why or why not?
d.
What recursive call to
quickSort
occurs next?
3.
Consider the merge step of the merge sort.
a.
What is the minimum number of comparisons needed to merge two subarrays each of size
n
/
2?
b.
Give a recurrence relation that counts the number of comparisons made in the best case.
c.
Make an educated guess at the solution to the recurrence relation.
4.
How many comparisons does quick sort require in the worst case when median-of-three partitioning is used?
What is the Big Oh for the worst case?
5.
Show the steps that a radix sort takes when sorting the following array of
Integer
objects:
783 99 472 182 264 543 356 295 692 491 94
6.
Show the steps that a radix sort takes when sorting the following array of strings into alphabetical order:
joke
book
back
dig
desk word fish
ward
dish
wit
deed
fast
dog
bend
7.
Describe how a card player can use a radix sort to sort a hand of cards.
8.
Consider a collection of
Comparable
objects that is represented by a chain of linked nodes. Suppose that you want to
provide a sort operation for this collection.
a.
Implement a private method that merges two sorted chains into one new sorted chain.
b.
The method described in Part
a
could be part of a merge sort of a sorted chain. Describe how you could
implement such a sort.
9.
Recall that a sorting algorithm is stable if it does not change the relative order of objects that are equal. What sorting
algorithms in this chapter and the previous one are stable?
10.
Segment 9.7 showed that you can compute the efficiency of merge sort by solving the recurrence relation
t
(
n
)
=
2
t
(
n
/
2)
+
n
when
n
>
1
t
(1)
=
0
Prove by induction that
t
(
n
)
=
n
log
2
n
.
