76 SORTING ALGORITHMS
This is very efficient, and so you might wonder why any of the other sorting
algorithms are even used.
The issue in this case becomes space efficiency. In sorts we’ve seen, we need
extra space for at most one additional record as we are swapping. In this case,
the space needs are more significant. If we use arrays for the buckets, these will
need to be extremely large arrays. In fact, they will need to be the size of the
original list, because we can’t assume that the keys will be uniformly distrib-
uted among the buckets as in Fig. 3.2. The chance that the keys will be distrib-
uted equally among the buckets is the same as the chance that they will all be
in the same bucket. Both can happen. Using arrays means that we will need
10 N additional space if the keys are numeric, 26N additional space if the keys
are alphabetic, and even more if the keys are alphanumeric or if case matters in
alphabetic characters. If we use arrays, we also have the time to copy the
records to the buckets in the distribution step and from the buckets back into
the original list in the coalescing step. This means each record will be “moved”
2 M times. If the records are large, this can take a substantial amount of time.
An alternative is to use a linked list structure for the records. Now, putting a
record into a bucket just requires changing a link, and coalescing the buckets
again just requires changing links. There is still significant space overhead,
because most implementations of linked lists will require 2 to 4 bytes per link,
making the total additional space needs 2N to 4N bytes.3.4.2
- Use the RadixSort algorithm to sort the list [1405, 975, 23, 9803, 4835,
2082, 7368, 573, 804, 746, 4703, 1421, 4273, 1208, 521, 2050]. Show the
buckets for each pass and the list after each bucket coalescing step. - Use the RadixSort algorithm to sort the list [117, 383, 4929, 144, 462,
1365, 9726, 241, 1498, 82, 1234, 8427, 237, 2349, 127, 462]. Show the
buckets for each pass and the list after each bucket coalescing step. - Another way of looking at radix sort is to consider the key as just a bit pat-
tern. So, if the keys are 4-byte integers, they are just considered as 32 bits,
and if the keys are strings of 15 alphanumeric characters (15 bytes), they are
just considered as 120 bits. These bit streams are then subdivided into pieces,
which determine the number of passes and the number of buckets. So, if we
have 120-bit keys, we might do 12 passes with 10-bit pieces, 10 passes with
12-bit pieces, or 5 passes with 24-bit pieces.
■3.4.2 EXERCISES