Radix Sort: Sample program for Radix Sort

This C program will sort a given array using Radix Sort

#define NUMELTS 100
# include <stdio.h>
#include <conio.h>
#include <math.h>
void radixsort(int a[],int);
void main()
{
	int n,a[20],i;
	clrscr();
 	printf("enter the number :");
	scanf("%d",&n);
	printf("ENTER THE DATA -");
	for(i=0;i<n;i++)
	{
	      printf("%d.  ",i+1);
	      scanf("%d",&a[i]);
   	}
	radixsort(a,n);
	getch();
}
void radixsort(int a[],int n)
{
	int rear[10],front[10],first,p,q,exp,k,i,y,j;
	struct
	{
		int info;
  		int next;
	}node[NUMELTS];
	for(i=0;i<n-1;i++)
	{
		node[i].info=a[i];
  		node[i].next=i+1;
	}
	node[n-1].info=a[n-1];
	node[n-1].next=-1;
	first=0;
	for(k=1;k<=2;k++)      //consider only 2 digit number
	{
		for(i=0;i<10;i++)
		{
			front[i]=-1;
		      	rear[i]=-1;	
		}
		while(first!=-1)
		{
		       p=first;
		       first=node[first].next;
		       y=node[p].info;
		       exp=pow(10,k-1);
		       j=(y/exp)%10;
		       q=rear[j];
		       if(q==-1)
               	           front[j]=p;
		       else
		            node[q].next=p;
			    rear[j]=p;
 		}
    		for(j=0;j<10&&front[j]==-1;j++);
		first=front[j];
    		while(j<=9)
                 {
      		        for(i=j+1;i<10&&front[i]==-1;i++);
		        if(i<=9)
			{
				p=i;
	                         node[rear[j]].next=front[i];
			}
			j=i;
			}
			node[rear[p]].next=-1;
         	}
		//copy into original array
		for(i=0;i<n;i++)
		{
			a[i]=node[first].info;
			first=node[first].next;
		}
		cprintf("DATA AFTER SORTING:");
		for(i=0;i<n;i++)
		printf("%d .   %d",i+1,a[i]);
	}

Explaination : Original, unsorted list:

170, 45, 75, 90, 2, 24, 802, 66

Sorting by least significant digit (1s place) gives:

170, 90, 2, 802, 24, 45, 75, 66

Notice that we keep 2 before 802, because 2 occurred before 802 in the original list, and similarly for pairs 170 &

90 and 45 & 75. Sorting by next digit (10s place) gives:

2, 802, 24, 45, 66, 170, 75, 90

Sorting by most significant digit (100s place) gives:

2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item

can be placed in its correct bucket without having to be compared with other items.

Some LSD radix sort implementations allocate space for buckets by first counting the number of keys that belong in

each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array.

Consider the previous list of keys viewed in a different way:

170, 045, 075, 090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:

2 (bucket size for digits of 0: 170, 090)

2 (bucket size for digits of 2: 002, 802)

1 (bucket size for digits of 4: 024)

2 (bucket size for digits of 5: 045, 075)

1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

2 (bucket size for digits of 0: 002, 802)

1 (bucket size for digits of 2: 024)

1 (bucket size for digits of 4: 045)

1 (bucket size for digits of 6: 066)

2 (bucket size for digits of 7: 170, 075)

1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)

1 (bucket size for digits of 1: 170)

1 (bucket size for digits of 8: 802)

At least one LSD radix sort implementation now counts the number of times that each digit occurs in each column for

all columns in a single counting pass. Other LSD radix sort implementations allocate space for buckets dynamically

as the space is needed.