Why Radix Sort?
Sorting algorithms are an essential part of our daily life. We might not notice it but from emails listed by date to not dying all of your white shirts pink, all of it involves sorting. To formally define a sorting algorithm we can say a sorting algorithm is used to rearrange a given array according to the comparison operator that is applied to it. You can read in detail about this from the link mentioned below:
Classification of Sorting Algorithms — GeeksforGeeks.
Our focus today will be on a non-comparison based sort. Now you might ask how would there be sorting if there is no comparison? This can be answered by understanding the following concept. There are two types of sorting algorithms, comparison based and non-comparison based. The main difference between a comparison based and a non-comparison based algorithm is comparison decision. Comparison based algorithms compare elements in an array to arrange them according to the operator while non-comparison based algorithms work on assumptions made on the data that is being processed to reach the output. Non-comparison based algorithms are also called Linear sorting algorithms. They rely on performing integer arithmetic on keys to define the comparison.
Another question that I would like to address here is why we need non-comparison sort when we already have a variety of comparison sorts available. It is because any comparison sort would normally take O(n²) time to sort an array while any non-comparison sort can sort the same array in O(n) time. This’ll be discussed further once we understand what a radix sort is and how it works.
INTRODUCTION TO RADIX SORT
Before we tackle the actual algorithm and how it works, let us understand the literal meaning of the word and how it falls back to the algorithm. Radix is the Latin word for “root”. The radix or base of a number is the number of unique digits used to represent that number. For example, the base of a decimal number is 10 or the base of a binary number is 2. Radix stands for the same concept and has the same meaning in radix sort. This might seem confusing in the first go but don’t lose heart just yet. It is much easier than it sounds!
Radix sort is a sorting algorithm that processes the elements of an array (integers) by grouping them by their individual digits. It can be said that the numbers are grouped with respect to their radix. Each radix is used as a key to implement counting sort or bucket sort to sort the given algorithm.
It’ll be easier to comprehend using a daily life example like sorting the names of students in a class.
These names are to be sorted in an alphabetical order. In the first step the names are to be grouped according to the first letter of the name and the same process can be repeated till (comparing each letter with every step) all the names are sorted in alphabetical order. How many radix would be there in such a situation?
UNDERSTANDING THE WORKING
Step 1: Find the maximum element.
Step 2: Check digit count of maximum element. (The number of digits of the maximum element makes the range of the sorting method used.)
Step 3: Arrange numbers according to least significant digit (lsd). (This requires you to sort the elements on the basis of the digit in the units place of each element(least significant place).)
Step 4: Repeat step 3 and arrange the numbers according to the next significant digit. (This is, more often than not, the second last digit of the number.)
Step 5: The above steps should be repeated till the most significant digit has been used to sort the numbers.
NOTE: Only stable sorting algorithms are used in the sorting process like counting sort and hence the numbers with the same digits in same places go in the same order as they were in the original, unsorted array. A sorting algorithm is said to be stable if the order of the same values in the output remains the same as in input array.
EXAMPLE
Consider this as the original array to be sorted using radix sort. You will notice how the above steps can be implemented in the given array using counting sort as a subroutine.
Step 1: Consider and isolate the Least Significant Digit of each number.
Step 2: Use counting sort to arrange the numbers in an ascending order according to the isolated digits as shown below.
Step 3: Now consider the second least significant digit of each number and isolate it.
Step 4: Repeat step 2 to obtain the sorted array.
Step 5: Repeat step 3 to isolate the most significant digit of each number in the given array.
Step 6: Repeat Step 2 to obtain the final sorted array.
Code (in c++):
#include <iostream>
using namespace std;
int get_max(int arr[], int n)
{
int mxm = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mxm)
mxm = arr[i];
return mxm;
}
void count_Sort(int arr[], int n, int exp) //subroutine algo
{
int output[n]; // output array
int i, count[10] = { 0 };
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
count[i] += count[i — 1];
for (i = n — 1; i >= 0; i — ) {
output[count[(arr[i] / exp) % 10] — 1] = arr[i];
count[(arr[i] / exp) % 10] — ;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void radix_sort(int arr[], int n)
{
int m = get_max(arr, n);
for (int exp = 1; m / exp > 0; exp *= 10)
count_Sort(arr, n, exp);
}
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << “ “;
}
int main()
{
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = sizeof(arr) / sizeof(arr[0]);
radix_sort(arr, n);
print(arr, n);
return 0;
}
TIME COMPLEXITY
Time complexity of Radix sort in reference to the above example can be calculated on the basis of the following information:
Here, n=7, b=10 and d=3 where “n” denotes the number of elements in the array, “b” denotes the range in which the keys lie (here it is 0–9) and “d” denotes the number of iterations required to reach the desired output or sort the whole array. Now we know that the time complexity of counting sort is O(n+k) where “k” denotes the keys, and counting sort has been used as a subroutine in the above algorithm, so the time complexity of the above code is O(d(n+b)). The asymptotic analysis of the same is given below and can be derived using the same explanation as given above.
Worst Case Time complexity: O ((n+b)d)
Average Case Time complexity: O ((n+b)d)
Best Case Time complexity: O ((n+b)d)
Space Complexity: O(n+k)
Sorting In Place: No
Stable: Yes
CONCLUSION
- Radix Sort is one of the most efficient and fastest linear sorting algorithms. It is simple to understand and easy to implement.
- It normally uses counting sort as a subroutine.
- Counting sort can only cover numbers in the range of 1 to k in the time complexity of O(n). If we implement counting sort on the numbers in the range of 1 to k² then the time complexity becomes O(nlogn), which is equal to the time complexity of any comparison based sort.
- Radix Sort can sort numbers in the range of 1 to k² in O(nd) time as we;ve derived above.
- So, it can be said that Radix Sort can handle larger keys more efficiently as compared to Counting Sort.
- Radix sort is almost equally efficient as the best comparison-based sorts (and worse if keys are much longer than log n).
REFERENCES:
