Java Reference
In-Depth Information
Algorithm
radixSort(a, first, last, maxDigits)
//
Sorts the array of positive decimal integers
a[first..last]
into ascending order;
//
maxDigits
is the number of digits in the longest integer.
for
(i = 0
to
maxDigits
-
1)
{
Clear
bucket[0]
,
bucket[1]
, . . . ,
bucket[9]
for
(index = first
to
last)
{
digit
=
digit
i
of
a[index]
Place
a[index]
at end of
bucket[digit]
}
Place contents of
bucket[0]
,
bucket[1]
, . . . ,
bucket[9]
into the array
a
}
This algorithm uses an array of buckets. The nature of a bucket is unspecified, but after you
read Chapter 10, you will see that a bucket can be an instance of the ADT queue.
Question 4
Trace the steps that the algorithm
radixSort
takes when sorting the following
array into ascending order:
6340 1234 291 3 6325 68 5227 1638
If an array contains
n
integers, the inner loop in the previous algorithm iterates
n
times. If each inte-
ger contains
d
digits, the outer loop iterates
d
times. Thus, the radix sort is O(
d
x
n
). The
d
in this
expression tells us that the actual running time for a radix sort depends on the size of the integers.
But on a computer, the typical integer is restricted in size to about 10 decimal digits, or 32 bits. As
long as
d
is fixed and is much smaller than
n,
radix sort is simply an O(
n
) algorithm.
Note:
Although radix sort is an O(
n
) algorithm for certain data, it is not appropriate for all data.
Question 5
One of the difficulties with the radix sort is that the number of buckets depends on
the kind of strings you are sorting. You saw that sorting integers requires 10 buckets; sorting
words requires at least 26 buckets. If you use radix sort to alphabetize an array of words, what
changes would be necessary to the given algorithm?
9.23
Figure 9-10 summarizes the efficiencies of the sorting algorithms presented in this chapter and the
previous chapter. Although a radix sort is fastest, it is not always applicable. The merge sort and
quick sort are generally faster than any of the other algorithms.
