Java Reference
In-Depth Information
Initial List:
27
91
1
97
17
23
84
28
72
5
67
25
First pass
(on right digit)
Second pass
(on left digit)
0
1
1
5
0
1
91
1
17
23
25
27
28
72
2
2
23
3
3
84
4
5
4
5
5
25
67
6
7
8
6
7
8
27
97
17
67
72
84
28
9
91
97
9
91
1
72
23
84
5
25
27
97
17
67
28
Result of first pass:
Result of second pass:
1
5
17
23
25
27
28
67
72
84
91
97
Figure7.17 An example of Radix Sort for twelve two-digit numbers in base ten.
Two passes are required to sort the list.
a large key range requires an unacceptably large array B . Thus, even the extended
Binsort is useful only for a limited key range.
A further generalization to Binsort yields a bucket sort. Each bin is associated
with not just one key, but rather a range of key values. A bucket sort assigns records
to bins and then relies on some other sorting technique to sort the records within
each bin. The hope is that the relatively inexpensive bucketing process will put
only a small number of records in each bin, and that a “cleanup sort” within the
bins will then be relatively cheap.
There is a way to keep the number of bins and the related processing small
while allowing the cleanup sort to be based on Binsort. Consider a sequence of
records with keys in the range 0 to 99. If we have ten bins available, we can first
assign records to bins by taking their key value modulo 10. Thus, every key will
be assigned to the bin matching its rightmost decimal digit. We can then take these
records from the bins in order and reassign them to the bins on the basis of their
leftmost (10's place) digit (define values in the range 0 to 9 to have a leftmost digit
of 0). In other words, assign the ith record from array A to a bin using the formula
A[i]/10 . If we now gather the values from the bins in order, the result is a sorted
list. Figure 7.17 illustrates this process.
Search WWH ::




Custom Search