Radix Sort

 

#include<stdio.h>

#include<unistd.h>

#include<stdlib.h>

int find_kthdigit(int a,int k)

{

 

//printf("\n val is %d k is %d ",a,k); 

int rem;

while(k--)

{

 

a=a/10;

 

}

rem=a%10;

return rem;

}

void countsort(int *a,int k ,int n)

{

int i,j;

 

int *count=(int*)malloc(sizeof(int)*n);

memset(count,0,10);

for(i=0;i<n;i++)

{

count[find_kthdigit(a[i],k)]++;

 

 

}

 

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

count[i]+=count[i-1];

 

int *temp=(int *)malloc(sizeof(int)*n);

 

for(i=n-1;i>=0;i--)

{

temp[count[find_kthdigit(a[i],k)]-1]=a[i];

count[find_kthdigit(a[i],k)]--;

}

 

 

for(i=0;i<n;i++)

a[i]=temp[i];

 

 

free (temp);

}

 

 

void radixsort(int *a ,int k ,int n)

{

int i,j;

for(i=0;i<k;i++)

{countsort(a,i,n);

 

}

}

 

int main()

{

 

 

int *a;

int n,i;

printf("\n Enter The size of the Data To Sort\n");

scanf("%d",&n);

a=(int *)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

a[i]=rand()%(n+1)+100;

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

radixsort(a,3,n);

gettimeofday(&tv_end,NULL);

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n---------------------\n Time Taken is %g \n",((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)*0.000001));

return 0;

}