Apr 5
Radix Sort by Saatvik Sinha
Today I will explain to you guys an interesting sorting technique in brief. It is called- Radix Sort. Let’s get started.
In this method, the respective digits of the numbers are used to sort the elements, starting from the least significant one to the most significant. All numbers should be of same length, that is, numbers with less number of digits than the largest one should be appended with 0s in the place of more significant digits. For example, in the list of numbers [1, 56, 782, 3, 40], the numbers should actually be treated as [001, 056, 782, 003, 040].
Radix sort is a non-comparison based technique. First, we create buckets of from 0 to 9. Then we iterate through the list and check the digit at one’s place of all the numbers, putting them into respective buckets. At the end of the iteration, the numbers are put back in the new order into the list. Next, we move on to tens place and check the digits, put the numbers into respective buckets and put them back into list for next iteration. Using this method, after the last iteration where the most significant digits were taken care of, we get a sorted list.
Let us understand the process of radix sort using following example-
Given list of numbers is [15, 1, 321, 10, 802, 2, 123, 90, 109, 11]
First we make the numbers of equal length, i.e., 3:
[015, 001, 321, 010, 802, 002, 123, 090, 109, 011]
1st iteration- we put digits into buckets from 0–9 based on ones place.
0: 010, 090
1: 001, 321, 011
2: 802, 002
3: 123
4: -
5: 015
6: -
7: -
8: -
9:109
Create new list = [010, 090, 001, 321, 011, 802, 002, 123, 015, 109]
2nd iteration- Put digits into buckets based on tens place.
0: 001, 802, 002, 109
1: 010, 011, 015
2: 321, 123
3: -
4: -
5: -
6: -
7: -
8: -
9: 090
Create new list = [001, 802, 002, 109, 010, 011, 015, 321, 123, 090]
Final iteration- Put digits into buckets based on hundreds place.
0: 001, 002, 010, 011, 015, 090
1: 109, 123
2: -
3: 321
4: -
5: -
6: -
7: -
8: 802
9: -
Final list = [1, 2, 10, 11, 15, 90, 109, 123, 321, 802]
As we can clearly see, our final list is sorted.
Radix sort is a stable sorting algorithm like bucket and count sort.
The time complexity of the algorithm is O(nk) while space complexity is O(n+k) where n is number of buckets and k is size of each bucket.
Radix sort is used in computers where the records are keyed by multiple fields.
