//Radix Sort
#include<stdio.h>
int getMax(int a[], int n)
{
int i, max=a[0];
for(i=1; i<n; i++)
if(a[i]>max)
max=a[i];
return max;
}
void accpet(int a[], int n)
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
}
void display(int a[],int n)
{
for(int i=0; i<n; i++)
printf("%d\t",a[i]);
}
void countingsort(int a[], int n, int pos)
{
int res[20], i, cnt[10]={0};
for(i=0; i<n; i++)
cnt[(a[i]/pos)%10]++;
for(i=1; i<10; i++)
cnt[i] += cnt[i-1];
for(i=n-1; i>=0; i--)
{
res[cnt[ (a[i]/pos)%10]-1]=a[i];
cnt[(a[i]/pos)%10]--;
}
for(i=0; i<n; i++)
a[i]=res[i];
}
void radixsort(int a[], int n)
{
int m=getMax(a,n);
for(int pos=1,pass=1; m/pos>0; pos*=10, pass++)
{
countingsort(a, n, pos);
printf("\nAfter pass %d: ",pass);
display(a, n);
}
}
int main()
{
int a[20], n;
printf("How many elements:");
scanf("%d", &n);
printf("\nEnter the %d elements:\n",n);
accpet(a,n);
radixsort(a,n);
printf("\n>>Sorted Elements<<\n");
display(a, n);
return 0;
}
