Count Sort

 

#include<stdio.h>

#include<unistd.h>

#include<stdlib.h>

#include<string.h>

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

{

int i;

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

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

b[a[i]]++;

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

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

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

{

temp[b[a[i]]-1]=a[i];

b[a[i]]--;

}

 

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

a[i]=temp[i];

free(temp);

}

 

int main()

{

int *a,*count;

 

int n,i;

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

scanf("%d",&n);

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

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

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

a[i]=rand()%(n);

memset((void *)count,0,n);

struct timeval tv_start,tv_end;

gettimeofday(&tv_start,NULL);

countsort(a,count,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));

free(a);

free(count);

return 0;

}