Data Structures and Abstractions with Java (3rd ed.) [Carrano 2011-09-23]

Chapter 10 Project 2.

Implement the radix sort, as given in Segment 9.21 of Chapter 9, by using a queue for each bucket.

9.2.1

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.

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.