Page 230 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

1 (bucket size for digits of 6: 066) Notes
2 (bucket size for digits of 7: 170, 075)
1 (bucket size for digits of 9: 090)
A third and final counting pass on the most significant digit of each key will produce an array of
bucket sizes:
6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)
1 (bucket size for digits of 1: 170)

1 (bucket size for digits of 8: 802)
Let us see another example.

Example:
Having the following list, let’s try to use radix sort to arrange the numbers from lowest to
greatest:

Unsorted list: 12, 8, 92, 7, 100, 500.
Because there are numbers with 3 digits, we can write the initial list like this: 012, 008, 092, 007,
100, 500.

Now by using the LSD, the sorting may begin with step 1:
Write all the numbers that have one of the following digit as the LSD of the numbers from the
list:
0:100, 500
1:
2:012, 092
3:
4:
5:
6:
7:007
8:008
9:

Also, if you have two numbers with the same digit like 012 and 092, you write them in the order
from the list.
Now, the order of the numbers according to step 1 is: 100, 500, 012, 092, 007, 008, which differs a
bit from the initial list.
We repeat step 1, but now we use the second digit :
0:100, 500, 007, 008
1:012
2:
3:
4:

LOVELY PROFESSIONAL UNIVERSITY 223