Radix
Sort
Consider an array A= { 54, 33, 25, 17, 09, 37, 13 }.
In radix sort traverse
array from left to right. Check maximum no. of digits in the array. In the above case, it is 2 so it will have
2-pass i.e, in the second pass information will be in sorted.
Traverse array
from left to right, check unit place
of each number in the array. Unit place of 54 is 4, so put 54 in bucket
4. Similarly, unit place of 33 is 3, so
put 33 in buctet 3. Similarly, check all
the numbers in the array and put those numbers in their respective buckets
Bucket
|
Pass-1
|
Pass-2
|
0
|
||
1
|
||
2
|
||
3
|
33,13
|
|
4
|
54
|
|
5
|
25
|
|
6
|
||
7
|
17,37
|
|
8
|
||
9
|
09
|
Now Merge the Output
of pass-1. Result is as follows A= {33,13,54,
25, 17, 37, 09}
Now tranverse output of Pass-1 from
left to right. Now check 10th
place of each number in the array. 10th
place of 33 is 3, put 33 in bucket 3. Similarly,
10th place of 13 is 1, put 13 in bucket 1. Similarly, check all the numbers in the array
and put those numbers in their respective buckets.
Bucket
|
Pass-1
|
Pass-2
|
0
|
09
|
|
1
|
13,17
|
|
2
|
25
|
|
3
|
33,13
|
33,37
|
4
|
54
|
|
5
|
25
|
54
|
6
|
||
7
|
17,37
|
|
8
|
||
9
|
9
|
Now Merge the output of pass-2. Result is as follows A= {09, 13, 17, 25, 33, 37,
54}
Note: if Maximum no. of digits is 3 then there will be 3
passes. If 4-digits, 4 passes etc.
The same can be done using the following calculation.
Consider an array A= { 54, 33, 25, 17, 09, 37, 13 }.
For Pass-1 Calculation (unit place)
54/100 = 54/1
= 54 =
54%10 = 4 Put 54 in bucket 4
33/100 = 33/1
= 33 =
33%10 = 3 Put 33 in bucket 3
25/100
=
25/1 = 25 = 25%10 = 5
Put 25 in bucket 5
17/100 = 17/1
= 17 =
17%10 = 7 Put
17 in bucket 7
09/100 = 09/1
= 09 =
09%10 = 9 Put 09 in bucket 9
37/100 = 37/1
= 37 =
37%10 = 7 Put 37 in bucket 7
13/100 = 13/1
= 13 =
13%10 = 3 Put 13 in bucket 3
Bucket
|
Pass-1
|
Pass-2
|
0
|
||
1
|
||
2
|
||
3
|
33,13
|
|
4
|
54
|
|
5
|
25
|
|
6
|
||
7
|
17,37
|
|
8
|
||
9
|
09
|
Merge output of pass-1 i.e., A= {33,13,54, 25, 17, 37, 09}
For Pass-2 Calculation (10th place).
33/101 = 33/10
= 3 =
3%10 = 3 Put 33 in bucket 3
13/101 = 13/10
= 1 =
1%10 = 1 Put 13 in bucket 1
54/101
=
54/10 = 5 = 5%10 = 5
Put 54 in bucket 5
25/101 = 25/10
= 2 =
2%10 = 2 Put
25 in bucket 2
17/101 = 17/10
= 1 =
1%10 = 1 Put 17 in bucket 1
37/101 = 37/10
= 3 =
3%10 = 3 Put 37 in bucket 3
09/101 = 09/10
= 0 =
0%10 = 0 Put 09 in bucket 0
Bucket
|
Pass-1
|
Pass-2
|
0
|
09
|
|
1
|
13,17
|
|
2
|
25
|
|
3
|
33,13
|
33,37
|
4
|
54
|
|
5
|
25
|
54
|
6
|
||
7
|
17,37
|
|
8
|
||
9
|
09
|
Now Merge the output of pass-2. Result is as follows A= {09, 13, 17, 25, 33, 37,
54}
C Program for radix sort.
#include<stdio.h>
#include<math.h>
struct node
{
int data;
struct node *link;
};
struct node * createnodes(int n)
{
int i;
struct node
*p,*first,*temp;
printf("Enter
elements\n");
for (i=0; i<n;
i++)
{
p= (struct node *)
malloc(sizeof(struct node));
scanf("%d", &p->data);
p->link = NULL;
if (i==0)
{
first=p;
}
else
{
temp=first;
while
(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=p;
}
}
return first;
}
void displaynodes(struct node *f)
{
struct node *temp;
temp=f;
while (temp!=NULL)
{
printf("%d-->",temp->data);
temp=temp->link;
}
printf("Null\n");
}
int MaxDigits(struct node *f)
{
struct node *temp;
int max,ct,n;
temp=f;
max=0;
while (temp!=NULL)
{
n=temp->data;
ct=0;
while(n>0)
{
ct++;
n=n/10;
}
if (ct>max)
{ max=ct; }
temp=temp->link;
}
return max;
}
void RadixSort(struct node *f1)
{
struct node
*first,*f[10],*r[10],*temp;
int max,i,j,k,p;
max=MaxDigits(f1);
first=f1;
for(i=0;i<max;i++)
{
for(j=0;
j<10;j++)
{
f[j]=NULL;
r[j]=NULL;
}
while(first!=NULL)
{
temp=first;
first=first->link;
p=(temp->data/pow(10.0,(float)i));
p=p%10;
if(f[p]==NULL
&& r[p]==NULL)
{
f[p]=temp;
r[p]=temp;
temp->link=NULL;
}
else
{
r[p]->link=temp;
temp->link=NULL;
r[p]=temp;
}
}
first=f[0];
for(k=1;k<10;k++)
{
if (first==NULL
&& f[k]==NULL)
first=NULL;
else if
(first==NULL && f[k]!=NULL)
first=f[k];
else
{
temp=first;
while(temp->link!=NULL)
{ temp=temp->link; }
temp->link=f[k];
}
}
printf("Result of Pass - %d
: ",i+1);
displaynodes(first);
}
}
void main()
{
int n;
struct node *first;
clrscr();
printf ("Enter
size of array/Linked list \n");
scanf("%d",&n);
first =
createnodes(n);
printf("Printing the elements from LL before sorting\n");
displaynodes(first);
RadixSort(first);
getch();
}
