Radix Sort algorithm is a computer-based sorting algorithm that allows for sorting digits from the least significant digit to the most significant or from the most significant to the least significant. For example, integer 2475 starting from its most significant digit (MSD) is “2 -the 1000th place”, and starting from its least significant digit (LSD) is “5 -the 1st place”. In this article, we will see about ‘Radix Sort Algorithm’.
Radix Sort Algorithm
Radix Sort Algorithm is a sorting algorithm used to place several integers in a specific order (ascending or descending). It is non-comparative because it avoids comparison when sorting elements. With Radix Sort Algorithm, an array of numbers is categorized by sorting based on the individual numbers of the digits in the array.
The number of passes in sorting arrays of numbers with Radix Sort is equal to the number of single figures present in the largest number of the array. For example, if 29876 is the largest number in an array of numbers, the number of passes required for such will be:
2 9 8 7 6
1 + 1 + 1 + 1 + 1 = 5 passes.
How does the Radix Sort Algorithm work?
1. It categorizes each digit in an array from least significant to most significant or from most significant to least.
2. With integers, the Radix Sort Algorithm arranges from the digits in the unit place then the tens place, then the hundreds, then the thousands, and so on, or from the thousands place to the hundreds place
to the tens place, then to the unit place.
3. Radix Sort uses counting sort to sort individual figures in each digit of an array. This can be done in either the MSD to the LSD or the LSD to the MSD
How to use the Radix Sort Algorithm?
A step by step procedure for the application of the Radix Sort Algorithm is as follows:
1. Create 10 slots or sections where digits from 0 to 9 can be categorized.
2. Identify the number of passes for your array by counting the number of figures that make up the array’s largest number.
3. Choosing to use the LSD to MSD method, recognize the LSD of each digit in the array to be sorted.
4. Arrange the array digits into the slots created from 0 to 9, using the unit place digits (which is the LSD place) for your arrangement.
5. Present your first pass by arranging the numbers as placed in the slots from “slot 0 (the smallest digit in base 10 numerical order)” to “slot 9 (the highest digit in base 10 numerical order).”
6. Repeat the same process in no.4 but with the tens place of the arranged digits in no.5 digits, after which you’ll present your second pass as you did in no.5
7. Keep repeating the processes in no.4 and no.5 accordingly till you reach the MSD, where the array will be adequately arranged in ascending order.
Using the LSD to MSD method, the process above can also be applied to the MSD to LSD method of the Radix Sort Algorithm.
Example:
Array: 786, 465 45, 90, 0, 3227, 8, 16, 5
75, 2232
Step 1: sections or slots 0 to 9
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Step 2: The highest number from the array of numbers is 3227, which has 4 figures. Therefore, the number of passes for the array is 4
Step 3: The bold numbers are the LSDs or the unit place digits of the array numbers:
786, 465, 45, 90, 0, 3227, 8, 16, 575, 2232
Step 4: The unit place of the array numbers in the slots
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 575 | |||||||||
| 90 | 465 | 786 | |||||||
| 0 | 2232 | 45 | 16 | 3227 | 8 |
Step 5: the first pass is 0, 90, 2232, 45, 465, 575, 16, 786, 3
Step 6: The bold numbers are the tens place digits of the pass (in the previous step):
0, 90, 2232, 45, 465, 575, 16, 786, 3227, 8.
Numbers 0 and 8 don’t have a tens place digit, so 0 will be assigned to them as a tens place digit.
Step 7: The tens place of the array numbers in the slots
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 08 | |||||||||
| 00 | 16 | 3227 | 2232 | 45 | 465 | 575 | 786 | 90 |
Step 8: The second pass is 0, 8, 16, 3227, 2232, 45, 465, 575, 786, 90
Step 9: The bold numbers are the hundreds place digits of the pass (in the former step):
0, 8, 16, 3227, 2232, 45, 465, 575, 786, 90.
Numbers 0, 8, 16, 45, and 90 will have 0 as their hundreds place digit.
Step 10: The hundreds place of the array numbers in the slots
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 090 | |||||||||
| 045 | |||||||||
| 016 | |||||||||
| 008 | 3227 | ||||||||
| 000 | 2232 | 465 | 575 | 786 |
Step 11: The third pass is 0, 8, 16, 45, 90, 2232, 3227, 465, 575, 786
Step 12: The bold numbers are the MSDs or the thousands placed digits of the pass (in the former step):
0, 8, 16, 45, 90, 2232, 3227, 465, 575, 786
Numbers 0, 8, 16, 45, 90, 465, 575, and 786 will have 0 as their thousands place digit.
Step 13: The thousands place of the array numbers in the slots
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0786 | |||||||||
| 0575 | |||||||||
| 0465 | |||||||||
| 0090 | |||||||||
| 0045 | |||||||||
| 0016 | |||||||||
| 0008 | |||||||||
| 0000 | 2232 | 3227 |
Step 14: The last pass to the array is 0, 8, 16,45, 90, 465, 575, 786, 2232, 3227.
The final sort gives a perfect numerical order of the initial unsorted array of numbers.
Radix Sort Algorithm Performance
• Radix Sort Algorithm Stability
The Radix Sort Algorithm is a stable integer sorting algorithm as it doesn’t use comparisons to categorize an array of integers
• Radix Sort Algorithm Time Complexity
This is categorized in the best-case, average-case, and worst-case time complexity.
• Radix Sort Algorithm Space Complexity
The Radix Sort algorithm has space complexity as it uses the counting sort algorithm in sorting elements.
Conclusion
Radix Sort Algorithm is used to sort numbers in an organized order. It allows numbers to be arranged from the LSD to the MSD (mostly used) or from the MSD to the LSD. It can categorize data such as integers, cards, mail, words, etc.
Frequently Asked Questions
1. What is Radix Sort applied to?
It is applied to data that allow lexicographical sorting, including integers and words. It can be used for sorting strings stably.
2. What is the best sorting algorithm?
Quicksort is considered the best, most efficient, and most effective sorting algorithm. It is the most used sorting algorithm. Once a pivot number is selected, Quicksort will use it to separate data easily, taking numbers higher than it to its right and numbers lower than it to its left.
3. Which sorting algorithm is the fastest?
Quicksort is considered the fastest sorting algorithm. It has the upper hand over the average sorting algorithms for inputs.
