3.4 RADIX SORT 73
can be removed by the exchange of two nonadjacent elements? Give an
example for a list with 10 elements.
3.4 Radix Sort
Radix sort uses key values to do the sort without actually comparing them to
each other. In this sort, we will create a set of “buckets” and will distribute the
entries into the buckets based on their key values. After collecting the values
and repeating this process for successive parts of the key, we can create a sorted
list. The distribution and collection has to be done very carefully for this to
work.
A process similar to this was used to sort cards manually. In some libraries,
before the days of computerized checkouts, when a book was taken out, a pic-
ture of it and a due date card was taken. The due date cards were numbered
and had a series of holes punched along one side. Some of these holes were cut
out to the side, creating notches along the edge that represented the number of
the card. As books were returned, the due date cards were removed and just
placed on a stack. A long needle was then placed through the first hole of the
stack of cards and it was lifted. The cards with a notch would stay on the table
and those without would remain on the needle. The two piles created were
recombined by placing the cards on the needle behind those with the notches.
The needle would then be moved to the next hole and the process repeated. As
long as the process was done to the holes in order and the arrangement of the
cards was never changed except for when the needle was raised, after process-
ing the final hole, the cards would be in numerical order.
This manual process would separate the cards by their least significant digit
at the beginning and by their most significant digit at the end. A computerized
version of this process to sort a set of numeric keys would use 10 buckets and
have the following algorithm:
RadixSort( list, N )
list the elements to be put into order
N the number of elements in the list
shift = 1
for loop = 1 to keySize do
for entry = 1 to N do
