//implementation of radix sort for number by linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void radix(int [],int ,int);
void main()
{
int a[100],n,m,i;
printf("\nEnter no of no and no of digits\n");
scanf("%d%d",&n,&m);
printf("\nEnter elemets\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
radix(a,n,m);
printf("\nSorted array is\n");
for(i=0;i<n;i++)
printf("\na[%d]=%d",i,a[i]);
getch();
}
void radix(int a[],int n,int m)
{
typedef struct node
{
int data;
struct node *next;
}NODE;
NODE *ptr,*prev,*start;
NODE *front[10],*rear[10];
int i,j,k=1,y,p;
start=NULL;
for(i=0;i<n;i++)
{
ptr=(NODE *)malloc(sizeof(NODE *));
ptr->data=a[i];
ptr->next=NULL;
if(start==NULL)
start=ptr;
else
prev->next=ptr;
prev=ptr;
}
for(i=1;i<=m;i++)
{
for(j=0;j<10;j++)
front[j]=NULL;
ptr=start;
while(ptr!=NULL)
{
y=((ptr->data)/k)%10;
if(front[y]==NULL)
{
front[y]=ptr;
rear[y]=ptr;
}
else
{
rear[y]->next=ptr;
rear[y]=ptr;
}
ptr=ptr->next;
}
start=NULL;
for(j=0;j<10;j++)
{
if(front[j]!=NULL)
{
if(start==NULL)
start=front[j];
else
rear[p]->next=front[j];
p=j;
}
}
rear[p]->next=NULL;
k=k*10;
}
ptr=start;
for(i=0;i<n;i++,ptr=ptr->next)
a[i]=ptr->data;
}
*******output*********
No comments:
Post a Comment