## COUNTING SORT IN C

In the code for counting sort, we assume that the input is an array A[1 . . . n] and  we require two other arrays: the array B[1 . . . n] holds the sorted output, and the array C[0 . . . k] provides temporary working storage. Here k = maximum element present in array.

Consider following elements to be sorted using counting sort : 2, 5, 3, 0, 2, 3, 0, 3

So we have in array A[1 . . . 8 ] :
 2 5 3 0 2 3 0 3

Now what we have to do is initialize the auxiliary array C[0 . . . k] with 0. Here k = 5.
So C[0 . . . 5] becomes :
 0 0 0 0 0 0

Next step is to count the frequency of each element and store it in their respective index position i.e here frequency of 0 = 2. So we place '2' at index position '0'. Similarly we place each element and the array becomes C[0 . . . 5] :
 2 0 2 3 0 1

Now we add the current index position with its previous index position and store it in the current index position i.e C[ i ] = C[ i ] + C[ i - 1 ] where 'i' starts from '1'.

So C[ 0 . . . 5 ] becomes :
 2 2 4 7 7 8

The final step is to place the elements in B[ 1 . . . 8 ] with reference to C[ 0 . . . 5 ] i.e  Now we treat elements in C[ 0 . . . 5 ] as index of B[ 1 . . . 8 ] and index of C[ 0 . . . 5 ] as elements of B[ 1 . . . 8 ]. So at index position '8' we have element '5' so we place '5' at index position of '8' of B[ 1 . . . 8 ] ( B[ 8 ] = 5 ) and we reduce the index position by '1' i.e 8-1 = 7. Now note that we have element '7'  in C[ 4 ] position but '4' is not present in the original array so we skip it and move to C[ 3 ] position, so we place '3' at index position '7' of B[ 1 . . . 8 ]. Similarly we place each element in B[ 1 . . . 8 ] and we get sorted array.

So the sorted array B[ 1 . . . 8 ]  is :
 0 0 2 2 3 3 3 5

## COUNTING SORT ALGORITHM

```// Counting Sort algorithm
```
`CountingSort(A,B,n,k)`
`   int C[0 . . . k ]`
`   for i=0 to k`
`      C[i]=0`
`   for j=1 to n`
`      C[A[j]] = C[A[j]] + 1;`
`   for i=1 to k`
`      C[i] = C[i] + C[i-1];`
`   for j=n downto 1`
```      B[C[A[j]]] = A[j];
C[a[j]] = C[A[j]] - 1;```

## COUNTING SORT PROGRAM IN C

`// Counting sort program in c`
```
#include<stdio.h>

void CountingSort(int a[], int sorted_array[], int max_element, int n);

int main()
{
int a,i,n;
int max_element, sorted_array;

printf("Enter number of elements in array : ");
scanf("%d",&n);

// Inputting elements
for(i=1;i<=n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}

// Displaying Elements before counting sort
printf("Items in the array are : ");
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}

// Finding Maximum element
max_element=a;

for(i=2;i<=n;i++)
{
if(a[i] > max_element)
{
max_element = a[i];
}
}

//Applying counting sort
CountingSort(a, sorted_array, max_element, n);

// Displaying elements after count sort
printf("\nElements after count sort : ");
for(i=1;i<=n;i++)
{
printf("%d ",sorted_array[i]);
}

return 0;
}

void CountingSort(int a[],int sorted_array[],int max_element, int n)
{
int aux_array[max_element];
int i,j;

// Initializing auxiliary array```
```        for(i=0;i<=max_element;i++)
{
aux_array[i]=0;
}
```
```        // Placing Frequency of each element in aux_array
for(j=1;j<=n;j++)
{
aux_array[a[j]]=aux_array[a[j]]+1;
}
```
```        // Adding elements of current and previous index position
for(i=1;i<=max_element;i++)
{
aux_array[i]=aux_array[i]+aux_array[i-1];
}
```
```        // Placing elements in sorted_array
for(j=n;j>=1;j--)
{
sorted_array[aux_array[a[j]]] = a[j];
aux_array[a[j]] = aux_array[a[j]] - 1;
}
}
```