Radix Sort

#include
<stdio.h>

#include
<conio.h>

#include
<math.h>

#define
TRUE 1

struct
list

{

int data;

struct
list *next;

};

typedef
struct list
Node;

Node *Head;

void
Display(Node *list,int w);

void
RadixSort(Node *list,int d);

power(int
x,int y);

void
main()

{

int
d=0,big,i,j,lim,count=0;

Node *list;

clrscr();

printf("\n\n\t\t
RADIX SORT ");

printf("\n\t\t ===== ====");

printf("\n\n\t
Enter limit :");

scanf("%d",&lim);

Head=(Node *)malloc(sizeof(Node));

list=Head;

do

{

count=count+1;

list->next=(Node *)malloc(sizeof(Node));

printf("\t Enter Data (%d):",count);

scanf("%d",&list->data);

if(count<lim)

list=list->next=(Node *)malloc(sizeof(Node));

else

{

list->next=NULL;

break;

}

}while(TRUE);

big=Head->data;

list=Head;

while(list->next)
/* Find Biggest Number */

{

if(big<list->data)

big=list->data;

list=list->next;

}

while(big>0) /*
Count Digits */

{

d=d+1;

big=big/10;

}

RadixSort(Head,d);

printf("\n\n\t\t
SORTED ARRAY ");

printf("\n\t\t======
=====\n\t");

Display(Head,d);

free(Head);

getch();

}

void
Display(Node *list,int w)

{

printf("\n");

while(list)

{

printf("\t
%0*d",w,list->data);

list=list->next;

}

}

void
RadixSort(Node *list,int d)

{

int
i,j;

Node *E[11],*F[11],*t,*p;

int
k;

p=list;

printf("\n\tARRAY
VALUES :");

Display(p,d);

printf("\n\n\t\t
Sorting Iterations are ");

printf("\n\t\t-------
---------- ---\n");

for(i=d;i>=1;i--)

{

for(j=0;j<10;j++)

F[j]=0;

while(p!=NULL)

{

k=(p->data);

k=(k/power(10,d-i))%10;

if(F[k]==0)

F[k]=p;

else

E[k]->next=p;

E[k]=p;

p=p->next;

}

j=0;

while(F[j]==0)

j=j+1;

p=F[j];

t=E[j];

for(k=j+1;k<10;k++)

if(F[k]!=0)

{

t->next=F[k];

t=E[k];

}

t->next=NULL;

Display(p,d);

}


/* End */

Head=p;

}

power(int x,int y)

{

int
t=1,i;

if(y==0)
return(1);

for(i=1;i<=y;i++)

t=t*x;

return(t);

}