Java Reference
In-Depth Information
FIGURE 9-9
Radix sort: (a) Original array and buckets after first distribution;
(b) reordered array and buckets after second distribution;
(c) reordered array and buckets after third distribution;
(d) sorted array
(a)
528
123
398
210
019
003
513
129
220
294
Unsorted array
Distribute integers into buckets according to the rightmost digit
210 220
123 003 513
294
0
1
2
3
Buckets
4
398 528
019 129
5
6
7
8
9
(b)
210
220
123
003
513
294
398
528
019
129
Distribute integers into buckets according to the middle digit
003
210 513 019
220 123 528 129
2
3
4
0
1
294 398
5
6
7
8
9
(c)
003
210
513
019
220
123
528
129
294
398
Distribute integers into buckets according to the leftmost digit
003 019
123 129
210 220 294
398
0
1
2
3
4
513 528
5
6
7
8
9
(d)
003
019
123
129
210
220
294
398
513
528
Pseudocode for Radix Sort
9.21
Our previous description of radix sort assumed that the integers to be sorted each contain the same number
of digits. Actually, this requirement is unnecessary as long as you get 0 when you ask for a digit that does
not exist. For example, if you ask for the hundreds digit of a two-digit integer, you should get 0.
The following algorithm describes a radix sort of an array of positive decimal integers. We
number the digits in each integer from the right beginning at zero. Thus, the units digit is digit 0,
the tens digit is digit 1, and so on.
 
Search WWH ::




Custom Search