Radix Sort Algorithm in Data Structure
Sarah Chen
What is the Radix Sort Algorithm?
Radix Sort is a non-comparative sorting algorithm. It works by grouping the individual digits of the elements to be sorted. A stable sorting technique is then used to organize the elements based on their radix. It is a linear sorting algorithm.
The sorting process involves the following properties:
- Finding the maximum element and acquiring the number of digits of that element. It gives us the number of iterations the sorting process will follow.
- Group the individual digits of the elements at the same significant position in each iteration.
- Grouping process will start from the least significant digit and end at the most significant digit.
- Sorting the elements based on digits at that significant position.
- Maintaining the relative order of elements that have the same key value. This property of the radix sort makes it a stable sort.
The final iteration will give us a completely sorted list.
Working of Radix Sort Algorithm
Let’s try to sort the list of integers in the above figure in an ascending order using the Radix Sort algorithm.
Here are the steps to perform the Radix Sorting process:
Step 1) Identify the element with the maximum value in the list. In this case, it is 835.
Step 2) Calculate the number of digits of the maximum element. 835 has 3 digits exactly.
Step 3) Determine the number of iterations based on step 2. 835 has 3 digits, meaning the number of iterations will be 3.
Step 4) Determine the base of the elements. Since this is a decimal system, the base will be 10.
Step 5) Start the first iteration.
a) First iteration
In the first iteration, we consider the unit place value of each element.
Step 1) Mod the integer by 10 to get the unit place of the elements. For example, 623 mod 10 gives us the value 3, and 248 mod 10 gives us 8.
Step 2) Use counting sort or any other stable sort to organize the integers according to their least significant digit. As seen From the figure, 248 will fall on the 8th bucket. 623 will fall on the 3rd bucket and so on.
After the first iteration, the list now looks like this.
As you can see from the above-given figure, the list is not sorted yet and requires more iteration to be fully sorted.
b) Second iteration
In this iteration, we will consider the digit at the 10th place for the sorting process.
Step 1) Divide the integers by 10. 248 divided by 10 gives us 24.
Step 2) Mod the output of step 1 by 10. 24 mod 10 gives us 4.
Step 3) Follow step 2 from the previous iteration.
After the second iteration, the list now looks like this
You can see from the above-given figure that the list is still not sorted completely as it is not in ascending order yet.
c) Third iteration
For the final iteration, we want to get the most significant digit. In this case, it’s the 100th place for each of the integers in the list.
Step 1) Divide the integers by 100… 415 divided by 100 gives us 4.
Step 2) Mod the result from step 1 by 10. 4 mod 10 gives us 4 again.
Step 3) Follow step 3 from the previous iteration.
As we can see, the list is sorted now in ascending order. The final iteration has been completed, and the sorting process is now finished.
Pseudocode of Radix Sort Algorithm
Here is the pseudo-code for the Radix Sort Algorithm
radixSortAlgo(arr as an array) Find the largest element in arr maximum=the element in arr that is the largest Find the number of digits in maximum k=the number of digits in maximum Create buckets of size 0-9 k times for j -> 0 to k Acquire the jth place of each element in arr. Here j=0 represents the least significant digit. Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace arr = sorted elements
C++ Program to Implement Radix Sort
#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
int maximum = arr[0];
for (int i = 1; i < n; i++) {
if (maximum < arr[i]) maximum = arr[i];
}
return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
const int limit = 10;
int result[size];
int count[limit] = {0};
// Calculating the count of each integers
for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
// Calculating the cumulative count
for (int j = 1; j < limit; j++) {
count[j] += count[j - 1];
}
// Sort the integers
for (int j = size - 1; j >= 0; j--) {
result[count[(arr[j] / position) % 10] - 1] = arr[j];
count[(arr[j] / position) % 10]--;
}
for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
// Get the largest element in the array
int maximum = getMaximum(arr, size);
for (int position = 1; maximum / position > 0; position *= 10)
countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {162, 623, 835, 415, 248};
int size = sizeof(arr) / sizeof(arr[0]);
radixSortAlgo(arr, size);
printResult(arr, size);
}
Output:
162 248 415 623 835
Python Program for Radix Sort Algorithm
#Radix Sort using python
def countingSortAlgo(arr, position):
n = len(arr)
result = [0] * n
count = [0] * 10 # Calculating the count of elements in the array arr
for j in range(0, n):
element = arr[j] // position
count[element % 10] += 1 # Calculating the cumulative count
for j in range(1, 10):
count[j] += count[j - 1] # Sorting the elements
i = n - 1
while i >= 0:
element = arr[i] // position
result[count[element % 10] - 1] = arr[i]
count[element % 10] -= 1
i -= 1
for j in range(0, n):
arr[j] = result[j]
def radixSortAlgo(arr): # Acquiring the largest element in the array
maximum = max(arr) # Using counting sort to sort digit by digit
position = 1
while maximum // position > 0:
countingSortAlgo(arr, position)
position *= 10
input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)
Output:
[162,248,415,623,835]
Complexity analysis of Radix Sort
There are two types of complexity to consider, space complexity and time complexity.
- Space complexity: O(n+b) where n is the size of the array and b is the base considered.
- Time complexity: O(d*(n+b)) where d is the number of digits of the largest element in the array.
Space Complexity of Radix Sort
Two features to focus on for space complexity
- Number of elements in the array, n.
- The base for representing the elements, b.
Sometimes this base can be greater than the size of the array.
The overall complexity is thus O(n+b).
The following properties of the elements in the list can make radix sort space inefficient:
- Elements with a large number of digits.
- Base of the elements is large, like 64-bit numbers.
Time Complexity of Radix Sort
You can use the counting sort as a subroutine, as each iteration will take O(n+b) time. If d iterations exist, the total running time becomes O(d*(n+b)). Here, “O” means the complexity function.
Linearity of Radix Sort
Radix Sort is linear when
- d is constant, where d is the number of digits of the largest element.
- b is not larger to a great extent compared to n.
Comparisons of Radix Sort with other comparative algorithms
As we’ve seen, the Radix sort’s complexity is based on a word or number size. It will have the same complexity for the average and best cases. And that is O(d*(n+b)). Also, it differs according to the sorting technique you use in the middle. For example, you can use counting sort or quick sort for the intermediate sorting algorithm inside the Radix sort.
Applications of Radix Sort Algorithm
Important Applications of Radix Sort are:
- Radix Sort can be used as a location finding algorithm where large ranges of values are used.
- It is used in constructing a suffix array in the DC3 algorithm.
- It is used In a sequential, random-access machine present in a typical computer where records are keyed.
