Radix Sort: A Comprehensive Explanation
Radix Sort is a non-comparative sorting algorithm that sorts numbers (or strings) digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD), or vice versa, depending on the implementation. It leverages a stable sorting algorithm like Counting Sort as a subroutine to sort the elements by each digit.
How Radix Sort Works
Radix Sort processes each digit of the numbers in a step-by-step manner. The key steps are:
- Find the Maximum Value:
- Determine the number with the largest number of digits in the input. This determines how many passes the algorithm will require.
- Find the Maximum Value:
- Iterate Over Each Digit Position:
- For each digit position (units, tens, hundreds, etc.):
- Sort the array based on the current digit using a stable sorting algorithm like Counting Sort.
- Repeat this for all digit positions.
- For each digit position (units, tens, hundreds, etc.):
- Iterate Over Each Digit Position:
- Combine Results:
- After processing all digit positions, the array is sorted.
- Combine Results:
Radix Sort Code
#include <stdio.h>
void input(int [],int);
void sort(int [],int);
int maxval(int [],int);
int no_of_digits(int);
void disp(int [],int);
int noofpasses(int [],int);
int main()
{
int ar[50],m;
printf("\nEnter the number of elements : ");
scanf("%d",&m);
printf("\nPlease enter the elements : ");
input(ar,m);
printf("\nBefore sorting elements are : ");
disp(ar,m);
sort(ar,m);
printf("\nAfter sorting elements are : ");
disp(ar,m);
return 0;
}
void input(int a[],int g)
{
int i;
for(i=0; i<g; i++)
scanf("%d",&a[i]);
}
void disp(int a[],int g)
{
int i;
for(i=0; i<g; i++)
printf("%d,",a[i]);
}
int maxval(int a[],int g)
{
int i,max;
max=a[0];
for(i=1; i<g; i++)
{
if(a[i]>max)
max=a[i];
}
return max;
}
int no_of_digits(int g)
{
int t=0;
while(g>0)
{
t++;
g=g/10;
}
return t;
}
int noofpasses(int a[],int g)
{
int p;
p=maxval(a,g);
p=no_of_digits(p);
return p;
}
void sort(int ar[],int g)
{
int noel[10],r=1,no_of_passes,i,bckt[10][50],j,pos,k,c;
no_of_passes=noofpasses(ar,g);
for(i=0; i<no_of_passes; i++)
{
for(j=0; j<10; j++)
noel[j]=0;
for(j=0; j<g; j++)
{
pos=(ar[j]/r)%10;
bckt[pos][noel[pos]++]=ar[j];
}
k=0;
for(j=0; j<10; j++)
{
for(c=0; c<noel[j]; c++)
ar[k++]=bckt[j][c];
}
r=r*10;
}
}
Example of Radix Sort
Input Array:
170,45,75,90,802,24,2,66170, 45, 75, 90, 802, 24, 2, 66
Step 1: Find the maximum element
- Maximum = 802 (3 digits)
Step 2: Sort by each digit (LSD to MSD)
- Sort by Units Place: [170,90,802,2,24,45,75,66][170, 90, 802, 2, 24, 45, 75, 66]
- Sort by Tens Place: [802,2,24,45,66,170,75,90][802, 2, 24, 45, 66, 170, 75, 90]
- Sort by Hundreds Place: [2,24,45,66,75,90,170,802][2, 24, 45, 66, 75, 90, 170, 802]
Final Sorted Array:
2,24,45,66,75,90,170,8022, 24, 45, 66, 75, 90, 170, 802
Time Complexity Analysis
Best, Average, and Worst Case: O(d⋅(n+b))O(d \cdot (n + b))
- dd: Number of digits in the largest number.
- nn: Total number of elements in the input array.
- bb: Base used for sorting (e.g., 10 for decimal numbers).
Breakdown:
- Counting Sort per digit: O(n+b)O(n + b).
- Total passes: dd (one for each digit).
- Overall complexity: O(d⋅(n+b))O(d \cdot (n + b)).
Special Cases:
- If the number of digits dd is treated as a constant (e.g., integers with a fixed number of digits), the complexity simplifies to O(n)O(n), making Radix Sort very efficient for such scenarios.
Space Complexity
- O(n+b)O(n + b):
- nn: For temporary storage used during Counting Sort.
- bb: For buckets to hold intermediate results.
- O(n+b)O(n + b):
Stability of Radix Sort
Radix Sort is inherently stable because it preserves the relative order of elements with the same digit value, provided the subroutine (e.g., Counting Sort) is stable.
Advantages of Radix Sort
- Efficient for Large Numbers with Few Digits:
- Handles large datasets efficiently when dd is small relative to nn.
- Efficient for Large Numbers with Few Digits:
- Non-Comparative Sorting:
- Does not involve comparisons, unlike QuickSort or MergeSort.
- Non-Comparative Sorting:
- Stable Sorting Algorithm:
- Suitable for applications where maintaining relative order is crucial.
- Stable Sorting Algorithm:
Disadvantages of Radix Sort
- Restricted to Specific Data Types:
- Primarily works on integers or strings that can be represented as positional digit sequences.
- Restricted to Specific Data Types:
- Higher Space Requirement:
- Requires additional memory for buckets and temporary arrays.
- Higher Space Requirement:
- Not In-Place:
- Needs extra storage, making it unsuitable for memory-constrained systems.
- Not In-Place:
Comparison with Other Sorting Algorithms
| Sorting Algorithm | Time Complexity | Space Complexity | Stability | Use Case |
|---|---|---|---|---|
| Radix Sort | O(d⋅(n+b))O(d \cdot (n+b)) | O(n+b)O(n + b) | Stable | Large datasets with fixed digits |
| QuickSort | O(nlogn)O(n \log n) | O(logn)O(\log n) | Not Stable | General-purpose sorting |
| MergeSort | O(nlogn)O(n \log n) | O(n)O(n) | Stable | Linked lists or large datasets |
| Counting Sort | O(n+k)O(n + k) | O(n+k)O(n + k) | Stable | Small ranges of integers |
Hope this tutorial has helped you for more codes please follow this website and my youtube channel for more details.