Radix sort
Introduction:
This algorithm is made to over come the conditions' of counting sort
Here we sort the numbers based radix. i.e., we sort the numbers based on the units place first then ten's place then hundred's place and soon..till the maximum number of decimal places.
The order is preserved during sorting.
Problem Statement:
Sort an array of n integers
Algorithm
1. we have an array of n numbers.
2. Following the same counting sort algorithm discussed here
3. we run counting sort but comparison is based on ith digit from end of all numbers in ith iteration.
4. After all iterations the array will be sorted.
Code :
#include <bits/stdc++.h>
using namespace std;
void radix_count_sort(int a[], int n, int ten_power)
{
unsigned long c[10] = {0}; // 0 to 9
int b[n] = {0};
for (int i = 0; i < n; i++)
{
c[(a[i] / ten_power) % 10]++; // ten_power th digit
}
for (int i = 1; i < 10; i++) // cummulative sum
{
c[i] += c[i - 1];
}
for (int i = n - 1; i >= 0; i--)
{
b[c[(a[i] / ten_power) % 10] - 1] = a[i]; // 0 based indexing
c[(a[i] / ten_power) % 10]--;
}
for (int i = 0; i < n; i++)
{
a[i] = b[i];
}
}
void radix_sort(int a[], int n)
{
int max = a[0];
for (int i = 0; i < n; i++)
{
if (max < a[i])
{
max = a[i];
}
}
int ten_power = 1;
while ((max / ten_power) > 0)
{
radix_count_sort(a, n, ten_power);
ten_power *= 10;
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<"\n";
}
}
int main()
{
int n;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
radix_sort(a, n);
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
printf("\n");
}
Complexity Analysis :
Time complexity is \(O(d*(n+10))\) ≈ \(O(d*n)\)
since base is 10 (here you can have base b other than 10... Try to do it..)
d is number of digits in largest number of the array and n is size of array.
for base b complexity is \(O(d*(n+b))\)