What is radix sort?
Radix Sort is an algorithm that sorts a list of numbers and comes under the category of distribution sort.
This sorting algorithm doesn’t compare the numbers but distributes them, it works as follows:
1. Sorting takes place by distributing the list of number into a bucket by passing through the individual digits of a given number one-by-one beginning with the least significant part. Here, the number of buckets are a total of ten, which bare key values starting from 0 to 9.
2. After each pass, the numbers are collected from the buckets, keeping the numbers in order
3. Now, recursively redistribute the numbers as in the above step ‘1’ but with a following reconsideration: take into account next most significant part of the number, which is then followed by above step ‘2’.
Radix sort in C:
#include <conio.h>
using namespace std;
#include <iostream>
#include <math>
void radixsort(int num\[\],int n)
{
int queue\[10\]\[10\],inc\[10\],i,j,k,c,exp;
for(i=0;i<4;i++)
{
exp=pow(10,i);
for(j=0;j<10;j++)
inc\[j\]=-1;
for(j=0;j<10;j++)
{
k=(num\[j\]/exp)%10;
inc\[k\]++;
queue\[k\]\[inc\[k\]\]=num\[j\];
}
for(k=0,c=0;k<10;k++)
{
j=0;
if(inc\[k\]!=-1)
while(j<=inc\[k\])
{
num\[c++\]=queue\[k\]\[j\];
j++;
}
}
}
}
Using the function
int main()
{
int num\[10\];
cout<<"Enter the elements to be sorted :\\n";
for(int i=0;i<10;i++)
cin>>num\[i\];
radixsort(num,10);
cout<<"The elemments in sorted order are :\\n";
for(int i=0;i<10;i++)
cout<<<" ";
getch();
}