C program to sort an array elements using Radix Sort
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info ;
struct node *link;
};
typedef struct node * NODE;
NODE bucket[10];
int n, a[20];
int largest()
{
int i, large = a[0];
for(i=0;i<n;i++) /*First find the largest number in the array*/
{
if(a[i] > large)
large = a[i];
}
return large;
}
void insert_rear(int item, int rem)
{
NODE cur, tmp;
tmp = (NODE)malloc(sizeof(struct node));
tmp->info = item;
tmp->link = NULL;
if(bucket[rem] == NULL)
{
bucket[rem] = tmp;
return;
}
else
{
cur = bucket[rem];
while(cur->link != NULL)
{
cur = cur->link;
}
cur->link = tmp;
}
}
void radix_sort()
{
NODE p;
int i, m,k, large, pass = 0, rem, divisor=1, j;
large = largest(); /*largest number in the array*/
printf("\nLargest Element is %d", large);
while(large != 0) /*Finds number of digits in the largest number*/
{
pass++;
large = large/10 ;
}
printf("\nNumber of passes are %d", pass);
for(m=1; m<=pass; m++)
{
printf("\n\n::::Pass %d::::", m);
for(i=0;i<=9;i++) /*initialize the buckets: Total 9 buckets*/
bucket[i] = NULL;
for(i=0;i<n;i++)
{
rem = (a[i] / divisor) %10;
insert_rear(a[i], rem);
}
for(i=0; i<=9 ; i++)
{
printf("\nbucket(%d) -> ",i);
p = bucket[i];
while(p!=NULL)
{
printf("%d ",p->info);
p = p->link;
}
}
/*Taking the elements of linked lists in array*/
i = 0;
for(k=0;k<=9;k++)
{
p = bucket[k];
while(p!=NULL)
{
a[i++] = p->info;
p = p->link;
}
}
divisor = divisor*10;
}
}
void main()
{
int i;
printf("\nEnter the number of elements in the list : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter element %d : ",i+1);
scanf("%d",&a[i]);
}
printf("\nUnsorted list is :\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
radix_sort();
printf("\nSorted list is :\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
Output:
Enter the number of elements in the list : 10
Enter element 1 : 179
Enter element 2 : 208
Enter element 3 : 306
Enter element 4 : 93
Enter element 5 : 859
Enter element 6 : 984
Enter element 7 : 55
Enter element 8 : 9
Enter element 9 : 271
Enter element 10 : 33
Unsorted list is :
179 208 306 93 859 984 55 9 271 33
Largest Element is 984
Number of passes are 3
::::Pass 1::::
bucket(0) ->
bucket(1) -> 271
bucket(2) ->
bucket(3) -> 93 33
bucket(4) -> 984
bucket(5) -> 55
bucket(6) -> 306
bucket(7) ->
bucket(8) -> 208
bucket(9) -> 179 859 9
::::Pass 2::::
bucket(0) -> 306 208 9
bucket(1) ->
bucket(2) ->
bucket(3) -> 33
bucket(4) ->
bucket(5) -> 55 859
bucket(6) ->
bucket(7) -> 271 179
bucket(8) -> 984
bucket(9) -> 93
::::Pass 3::::
bucket(0) -> 9 33 55 93
bucket(1) -> 179
bucket(2) -> 208 271
bucket(3) -> 306
bucket(4) ->
bucket(5) ->
bucket(6) ->
bucket(7) ->
bucket(8) -> 859
bucket(9) -> 984
Sorted list is :
9 33 55 93 179 208 271 306 859 984
