Java Reference
In-Depth Information
sorts the entries in
a[first]
through
a[after - 1]
. Note that
type
is either
byte
,
char
,
double
,
float
,
int
,
long
, or
short
.
9.20
The sorting algorithms that you have seen so far sort objects that can be compared. The
radix sort
does not use comparison, but to work, it must restrict the data that it sorts. For this restricted data,
the radix sort is O(
n
), and so it is faster than any other sort in this chapter. However, it is not suit-
able as a general-purpose sorting algorithm, because it treats array entries as if they were strings
that have the same length.
Let's look at an example of a radix sort of the following three-digit positive integers:
123 398 210 019 528 003 513 129 220 294
Notice that 19 and 3 are padded with zeros to make them three-digit integers. The radix sort begins
by grouping the integers according to their rightmost digits. Since a digit can have one of 10 values,
we need 10 groups, or
buckets
. If bucket
d
corresponds to the digit
d
, we place 123 into bucket 3,
398 into bucket 8, and so on. Figure 9-9a shows the result of this process. Notice that each bucket
must retain the order in which it receives the integers.
Looking at the buckets sequentially, we see that the integers are now in the following order:
210 220 123 003 513 294 398 528 019 129
We move these integers from the buckets to the original array. We then group the integers by their
middle digits, using the now empty buckets. Thus, 210 goes into bucket 1, 220 goes into bucket 2,
123 goes into bucket 2, and so on. Figure 9-9b shows the result of this pass.
The integers in the buckets are now in this order:
003 210 513 019 220 123 528 129 294 398
After moving these integers from the buckets back to the array, we group them by their leftmost
digits. Thus, 003 goes into bucket 0, 210 goes into bucket 2, 513 goes into bucket 5, and so on.
Figure 9-9c shows the result of this pass.
The integers in the buckets are now in their final sorted order:
003 019 123 129 210 220 294 398 513 528
Aside: Origin of the radix sort
During the early days of computing, data was stored on punched cards. Each card had 80 columns
in which to store 80 characters. Each column had 12 rows that were the possible positions for
holes. A machine called a card sorter distributed the cards among 12 bins according to the row
punched in the column chosen by the machine's operator. These bins are analogous to the buckets
in a radix sort. After running a stack of cards through the card sorter, the operator would gather the
cards a bin at a time to create a new stack. The cards would be run through the sorter again to sort
the next column of holes. By repeating this process, the operator could sort the cards.
