Java Reference
In-Depth Information
staticvoidradix(Integer[]A,Integer[]B,
intk,intr,int[]count){
//Count[i]storesnumberofrecordsinbin[i]
inti,j,rtok;
for(i=0,rtok=1;i<k;i++,rtok
*
=r){//Forkdigits
for(j=0;j<r;j++)count[j]=0; //Initializecount
//Countthenumberofrecordsforeachbinonthispass
for(j=0;j<A.length;j++)count[(A[j]/rtok)%r]++;
//count[j]willbeindexinBforlastslotofbinj.
for(j=1;j<r;j++)count[j]=count[j-1]+count[j];
//Putrecordsintobins,workingfrombottomofbin
//Sincebinsfillfrombottom,jcountsdownwards
for(j=A.length-1;j>=0;j--)
B[--count[(A[j]/rtok)%r]]=A[j];
for(j=0;j<A.length;j++)A[j]=B[j];//CopyBback
}
}
Figure7.18
The Radix Sort algorithm.
In this example, we have r = 10 bins and n = 12 keys in the range 0 to r
2
1.
The total computation is (n), because we look at each record and each bin a
constant number of times. This is a great improvement over the simple Binsort
where the number of bins must be as large as the key range. Note that the example
uses r = 10 so as to make the bin computations easy to visualize: Records were
placed into bins based on the value of first the rightmost and then the leftmost
decimal digits. Any number of bins would have worked. This is an example of a
Radix Sort, so called because the bin computations are based on the radix or the
base of the key values. This sorting algorithm can be extended to any number of
keys in any key range. We simply assign records to bins based on the keys' digit
values working from the rightmost digit to the leftmost. If there are k digits, then
this requires that we assign keys to bins k times.
As with Mergesort, an efficient implementation of Radix Sort is somewhat dif-
ficult to achieve. In particular, we would prefer to sort an array of values and avoid
processing linked lists. If we know how many values will be in each bin, then an
auxiliary array of size r can be used to hold the bins. For example, if during the
first pass the 0 bin will receive three records and the 1 bin will receive five records,
then we could simply reserve the first three array positions for the 0 bin and the
next five array positions for the 1 bin. Exactly this approach is taken by the Java
implementation of Figure 7.18. At the end of each pass, the records are copied back
to the original array.
