Radix sort is a linear sorting algorithm for integers and uses the concept of sorting names inalphabetical order. When we have a list of sorted names, the radix is 26 (or 26 buckets) becausethere are 26 letters in the English alphabet. So radix sort is also known as bucket sort. Observethat words are first sorted according to the first letter of the name. That is, 26 classes are used to arrange the names, where the first class stores the names that begin with A, the second class contains the names with B, and so on.
During the second pass, names are grouped according to the second letter. After the second pass, names are sorted on the first two letters. This process is continued till the nth pass, where n is the length of the name with maximum number of letters.
After every pass, all the names are collected in order of buckets. That is, first pick up the names in the first bucket that contains the names beginning with A. In the second pass, collect the names from the second bucket, and so on.
When radix sort is used on integers, sorting is done on each of the digits in the number. The sorting procedure proceeds by sorting the least significant to the most significant digit. While sorting the numbers, we have ten buckets, each for one digit (0, 1, 2, …, 9) and the number of passes will depend on the length of the number having maximum number of digts.
** Algorithm for radix sort **
Algorithm for RadixSort (ARR, N)
Step 1: Find the largest number in ARR as LARGE
Step 2: [INITIALIZE] SET NOP = Number of digits in LARGE
Step 3: SET PASS = 0
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5: SET I = 0 and INITIALIZE buckets
Step 6: Repeat Steps 7 to 9 while I<N-1
Step 7: SET DIGIT = digit at PASSth place in A[I]
Step 8: Add A[I] to the bucket numbered DIGIT
Step 9: INCEREMENT bucket count for bucket numbered DIGIT
[END OF LOOP]
Step 10: Collect the numbers in the bucket
[END OF LOOP]
Step 11: END
Example :- Sort the numbers given below using radix sort.
345, 654, 924, 123, 567, 472, 555, 808, 911
In the first pass, the numbers are sorted according to the digit at ones place. The buckets are pictured upside down as shown below.
After this pass, the numbers are collected bucket by bucket. The new list thus formed is used as an input for the next pass. In the second pass, the numbers are sorted according to the digit at the tens place. The buckets are pictured upside down.
In the third pass, the numbers are sorted according to the digit at the hundreds place. The buckets are pictured upside down
The numbers are collected bucket by bucket. The new list thus formed is the final sorted result. After the third pass, the list can be given as
123, 345, 472, 555, 567, 654, 808, 911, 924.
Complexity of Radix Sor :-
To calculate the complexity of radix sort algorithm, assume that there are n numbers that have to be sorted and k is the number of digits in the largest number. In this case, the radix sort algorithm is called a total of k times. The inner loop is executed n times. Hence, the entire radix sort algorithm takes O(kn) time to execute. When radix sort is applied on a data set of finite size (very small set of numbers), then the algorithm runs in O(n) asymptotic time.
*******************
Programming Example
*******************
1. Write a program to implement radix sort algorithm.
#include<stdio.h>
#include<conio.h>
void read(int a[], int n);
void print(int a[], int n);
int maximun(int a[], int n);
void radix(int a[],int n);
void main()
{
int a[50],n,i;
clrscr();
printf("\n\n\t Enter your element....>");
scanf("%d",&n);
read(a,n);
print(a,n);
printf("\n\t\t Array of radix short..");
radix(a,n);
for(i=0;i<n;i++)
{
printf("\n\t\t%d\n",a[i]);
}
getch();
}
void read(int a[], int n)
{
int i;
for(i=0;i<n;i++)
{
printf("\n\t array of element.a[%d]...>",i);
scanf("%d",&a[i]);
}
}
void print(int a[], int n)
{
int i;
for(i=0;i<n;i++)
{
printf("\n\t array of end element....>%d",a[i]);
}
}
int maximun(int a[], int n)
{
int i,max=a[0];
for(i=0;i<n;i++)
{
if(a[i]>max)
{
max=a[i];
}
}
return max;
}
void radix(int a[],int n)
{
int bucket[10][10],bucket_count[10];
int i,j,k,rem,divisor=1,pass,nop=0,larger;
larger=maximun(a,n);
while(larger>0)
{
nop++;
larger=larger/10;
}
for(pass=0;pass<nop;pass++)
{
for(i=0;i<10;i++)
{
bucket_count[i]=0;
}
for(i=0;i<n;i++)
{
rem=(a[i]/divisor)%10;
bucket[rem][bucket_count[rem]]=a[i];
bucket_count[rem]+=1;
}
i=0;
for(k=0;k<10;k++)
{
for(j=0;j<bucket_count[k];j++)
{
a[i]=bucket[k][j];
i++;
}
}
divisor=divisor*10;
}
}
All c programming & algorithm 