74 SORTING ALGORITHMS
bucketNumber = (list[entry].key / shift) mod 10
Append( bucket[bucketNumber], list[entry] )
end for entry
list = CombineBuckets()
shift = shift * 10
end for loop
We’ll begin by reviewing this algorithm. The calculation of bucketNumber
will pull a single digit out of a key. The division by shift will cause the key
value to be moved to the right some number of digits, and then the mod will
eliminate all but the units digit of the resulting number. On the first pass with
a shift value of 1, the division will do nothing, and the mod result will return
just the units digit of the key. On the second pass, shift will now be 10, so
the integer division and then the mod will return just the tens digit. On each
succeeding pass, the next digit of the key will be used.
TheCombineBuckets function will append the buckets back into one list
starting with bucket[0] through bucket[9]. This recombined list is the
starting point for the next pass. Because the buckets are recombined in order
and because the numbers are added to the end of each bucket list, the keys will
eventually be sorted. Figure 3.2 shows the three passes that would be done for
keys with three digits. To make this example simpler, all of the keys just use the
digits 0 through 3, so only four buckets are needed.
In looking at Fig. 3.2(c), you should see that if the buckets are again com-
bined in order, the list will now be sorted.■ 3.4.1 Analysis
An analysis of radix sort requires that we consider issues beyond just number of
operations, because in this case they are significant. How this particular algo-
rithm is implemented has an impact on its overall efficiency. We consider both
the time and space efficiency of this algorithm.
Each key is looked at once for each digit (or letter if the keys are alphabetic)
of the longest key. So, if the longest key has M digits and there are N keys,
radix sort has order O(M*N). But if we look at these two values, the size of
the keys will be relatively small when compared to the number of keys. For
example, if we have six-digit keys, we could have a million different records.
Recalling the discussion of Section 1.4 on rates of growth, we see that the size
of the keys is not significant, and this algorithm is of linear complexity, O(N).