Program of sorting using Radix sort

Program of Sorting using Radix Sort

# include<stdio.h>
# include<malloc.h>

struct  node
{
int info ;
struct node *link;
}*start=NULL;

main()
{
struct node *tmp,*q;
int i,n,item;

printf("Enter the number of elements in the list : ");
scanf("%d", &n);

for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&item);

/* Inserting elements in the linked list */

tmp= malloc(sizeof(struct node));
tmp->info=item;
tmp->link=NULL;

if(start==NULL)     /* Inserting first element */
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}    /*End of for*/

printf("Unsorted list is :\n");
display();
radix_sort();
printf("Sorted list is :\n");
display ();
}     /*End of main()*/

display()
{
struct node *p=start;
while( p !=NULL)
{
printf("%d ", p->info);
p= p->link;
}
printf("\n");
}     /*End of display()*/

radix_sort()
{
int i,k,dig,maxdig,mindig,least_sig,most_sig;
struct node *p, *rear[10], *front[10];

least_sig=1;
most_sig=large_dig(start);

for(k = least_sig; k <= most_sig ; k++)
{
printf("PASS %d : Examining %dth digit from right   ",k,k);
for(i = 0 ; i <= 9 ; i++)
{
rear[i] = NULL;
front[i] = NULL ;
}
maxdig=0;
mindig=9;
p = start ;
while( p != NULL)
{
/*Find kth digit in the number*/

dig = digit(p->info, k);
if(dig>maxdig)
maxdig=dig;
if(dig<mindig)
mindig=dig;

/*Add the number to queue of dig*/

if(front[dig] == NULL)
front[dig] = p ;
else
rear[dig]->link = p ;
        rear[dig] = p ;
        p=p->link;        /*Go to next number in the list*/
 }                                       /*End while */
              /* maxdig and mindig are the maximum amd minimum
               digits of the kth digits of all the numbers*/

printf("mindig=%d  maxdig=%d\n",mindig,maxdig);

/*Join all the queues to form the new linked list*/

start=front[mindig];
for(i=mindig;i<maxdig;i++)
{
if(rear[i+1]!=NULL)
rear[i]->link=front[i+1];
else
rear[i+1]=rear[i];
}
rear[maxdig]->link=NULL;
printf("New list : ");
display();
}  /* End for */

}           /*End of radix_sort*/

/* This function finds number of digits in the largest element of the list */
int large_dig()
{
struct node *p=start ;
int large = 0,ndig = 0 ;

while(p != NULL)
{
if(p ->info > large)
large = p->info;
p = p->link ;
}
printf("Largest Element is %d , ",large);
while(large != 0)
{
ndig++;
large = large/10 ;
}

printf("Number of digits in it are %d\n",ndig);
return(ndig);
}    /*End of large_dig()*/

/*This function returns kth digit of a number*/
int digit(int number, int k)
{
int digit, i ;
for(i = 1 ; i <=k ; i++)

{
digit = number % 10 ;
number = number /10 ;
}
return(digit);
}/*End of digit()*/