Page 229 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Each key is first figuratively dropped into one level of buckets corresponding to the value of the
rightmost digit. Each bucket preserves the original order of the keys as the keys are dropped
into the bucket. There is a one-to-one correspondence between the number of buckets and the
number of values that can be represented by a digit. Then, the process repeats with the next
neighboring digit until there are no more digits to process. In other words:
1. Take the least significant digit of each key.
2. Group the keys based on that digit, but otherwise keep the original order of keys.
3. Repeat the grouping process with each more significant digit.

The sort in step 2 is usually done using bucket sort or counting sort, which are efficient in this
case since there are usually only a small number of digits.

Example:
Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1s place) gives:
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90

Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
It is important to realize that each of the above steps requires just a single pass over the data,
since each item can be placed in its correct bucket without having to be compared with other
items.
Some LSD radix sort implementations allocate space for buckets by first counting the number of
keys that belong in each bucket before moving keys into those buckets. The number of times
that each digit occurs is stored in an array. Consider the previous list of keys viewed in a
different way:

170, 045, 075,090, 002, 024, 802, 066
The first counting pass starts on the least significant digit of each key, producing an array of
bucket sizes:

2 (bucket size for digits of 0: 170, 090)
2 (bucket size for digits of 2: 002, 802)
1 (bucket size for digits of 4: 024)
2 (bucket size for digits of 5: 045, 075)
1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of
bucket sizes:
2 (bucket size for digits of 0: 002, 802)
1 (bucket size for digits of 2: 024)

1 (bucket size for digits of 4: 045)

222 LOVELY PROFESSIONAL UNIVERSITY