Implement program of Counting Sort.

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<conio.h>

long int cnt=0;

void Counting_Sort(int *a,intn,int *b)

{

cnt++;

int max=a[0],i,j,*c;

cnt++;

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

{

cnt+=2;

if (a[i] > max)

{

cnt++;

max = a[i];

}

}

cnt++;

c=(int *)malloc((max+1)*sizeof(int));

cnt++;

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

{

cnt+=2;

c[i] =0;

}

cnt++;

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

{

cnt+=2;

c[a[j]] = c[a[j]] +1;

}

cnt++;

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

{

cnt+=2;

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

}

cnt++;

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

{

cnt+=3;

b[c[a[j]]-1] = a[j];

c[a[j]]=c[a[j]] - 1;

}

}

int *create_random_data(int n)

{

int *p,i;

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

if(p==NULL)

{

return NULL;

}

else

{

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

{

p[i]=rand()%n; 

}

}

return p;

}

int main()

{

clrscr();

int *a,*b,*c,i,n;

printf("Enter value for n:");

scanf("%d",&n);

a=create_random_data(n);

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

Counting_Sort(a,n,b);

printf("Sorted data:\n");

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

{

printf("%d\n",b[i]);

}

printf("Steps Count: %ld",cnt);

return 0;

}