Updated March 6, 2023
Introduction to Radix Sort in Data Structure
Radix sort is the algorithm that is followed for sorting a particular set or list of values by grouping the individual characters or digits at the same place after which each of the selected characters or elements are sorted based on increasing or decreasing order whichever is required. Radix sort internally makes the use of counting sort for sorting all the individual characters or numbers at a particular place and further collects the result to get the final sorted output. In this article, we will learn about the usage and the implementation of radix sort and also discuss its advantages and disadvantages followed by complexity analysis.
Working of Radix sort in data structures
Consider that we have an array containing 10 elements in it which are the numbers with at the most 3 digit wide. The radix algorithm will firstly sort all the elements at units place, then at tens place and further continues this process until the last significant place in our case up to hundreds place. Consider that we have the array of values [136,781,655,6,87,785,545,45,565,656].
In such case, the radix sort will work in the following way. Sorting the data three times to get the final sorted array. In the first round all the digits at the unit place and then in second round all the numbers within the same bucket of the same unit place will be sorted on the tens place. Further, the third round will be carried out for same tens digit and unit place and sort will be done for the hundreds place. Refer the following figure to observe how the radix sort is performed.
Example
Let us consider one example where we will sort a particular array in C programming language using radix sort.
// Implementation of radix sort using C programming language
#include <stdio.h>
// Retrieve the biggest number from all the elements of the radixArr
int retrieveLargest(int radixArr[], int n) {
int largestNo= radixArr[0];
for (int i = 1; i < n; i++)
if (radixArr[i] > largestNo)
largestNo= radixArr[i];
return largestNo;
}
// Take all the significant places and for each of them use the counting sort
void countingSort(int radixArr[], int size, int place) {
int finalResult[size + 1];
int largestNo= (radixArr[0] / place) % 10;
for (int i = 1; i < size; i++) {
if (((radixArr[i] / place) % 10) > largestNo)
largestNo= radixArr[i];
}
int count[largestNo+ 1];
for (int i = 0; i < largestNo; ++i)
count[i] = 0;
// Get the number of total elements
for (int i = 0; i < size; i++)
count[(radixArr[i] / place) % 10]++;
// Get the cumulative sum of all the totals calculated above
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Arrange all the elements in the sorted order in the final radixArr
for (int i = size - 1; i >= 0; i--) {
finalResult[count[(radixArr[i] / place) % 10] - 1] = radixArr[i];
count[(radixArr[i] / place) % 10]--;
}
for (int i = 0; i < size; i++)
radixArr[i] = finalResult[i];
}
// Radix sort which in turn uses the cunting sort for all the individual elements
void radixsort(int radixArr[], int size) {
// Get largestNo element
int largestNo= retrieveLargest(radixArr, size);
// Depending on the place value and using the counting sort sort the radixArr
for (int place = 1; largestNo/ place > 0; place *= 10)
countingSort(radixArr, size, place);
}
// Display the final sorted radixArr in the output
void displayradixArr(int radixArr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", radixArr[i]);
}
printf("\n");
}
// Controller for the radix sort which uses all the other fuctions
int main() {
int radixArr[] = {121, 432, 564, 23, 1, 45, 788};
int n = sizeof(radixArr) / sizeof(radixArr[0]);
radixsort(radixArr, n);
displayradixArr(radixArr, n);
}
The output of the execution of above program is as shown below-
Complexity Analysis
The time complexity of the radix sort is O((n+b)*logb(max)) where max is the maximum element of the array which is supplied as input and b is the base for number representation. That means we need to do n+b iterations log(max) number of times in radix sort.
Advantages
The advantages of the radix algorithm are that it works fast when the array elements have less range of the values that they can possess which results in short key.
The radix algorithms is used in DC3 and Manber’s algorithm in algorithms for suffix array construction.
Disadvantages
- The radix sort needs to be rewritten for each of the data types as it involves sorting which is based on letters or digits.
- As compared to other sorting algorithms used in data structures, the constant of the radix sort is greater in value.
- Quick sort makes the use of in place storing and hence it requires more space for radix sort algorithm as compared to quick sort.
Conclusion
Radix sort is the sorting algorithm or technique used in data structures that sorts all the result set by getting the maximum number of significant places in the elements and then for each individual significant place sort the elements on the place value of that element. For each of the individual sorting the radix sort makes the use of counting sort internally and finally accumulates the result to get the sorted output.
Recommended Articles
This is a guide to Radix Sort in Data Structure. Here we discuss Introduction, Working of Radix sort in data structures, advantages, and disadvantages. You may also have a look at the following articles to learn more –
