# Counting Sort Program In C

## 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[20],i,n;
int max_element, sorted_array[20];

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[1];

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;
}
}

#### Related Posts

Previous
Next Post »

// 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;
}

Let n=8

a[1 . . . 8] : 2 5 3 0 2 3 0 3
Elements are stored from index position 1.

// Initializing auxiliary array
for(i=0;i<=max_element;i++)
{
aux_array[i]=0;
}

aux_array[0...5]=0 0 0 0 0 0

// Placing Frequency of each element in aux_array
for(j=1;j<=n;j++)
{
aux_array[a[j]]=aux_array[a[j]]+1;
}

Now aux_array[0. . . 5] : 2 0 2 3 0 1
Elements are stored from index position 0.

/* Adding elements of current and previous index position of aux_array
for(i=1;i<=max_element;i++)
{
aux_array[i]=aux_array[i]+aux_array[i-1];
}
Note : We are placing elements from index position 1
So, aux_array[0]=2

aux_array[1]=aux_array[1]+aux_array[0]
aux_array[1] = 0 + 2 = 2
Now aux_array[1]=2 // i.e we have 2 at index position 1 of aux_array

Similarly on next loops :

aux_array[2] = aux_array[2]+aux_array[1]
aux_array[2] = 2+2 = 4
aux_array[2] = 4

aux_array[3] = aux_array[3]+aux_array[2]
aux_array[3] = 3+4 = 7
aux_array[3] = 7

and so on..

After loop is finished then we will have :
aux_array[0...5] = 2 2 4 7 7 8

// 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;
}

Here we are placing elements in ascending order in sorted_array

We have :
n=8

For j=8
a[1...8]=2 5 3 0 2 3 0 3
aux_array[0...5] = 2 2 4 7 7 8

sorted_array[aux_array[a[j]]] = a[j];
sorted_array[aux_array[a[8]]]
i.e sorted_array[aux_array[3]]
i.e sorted_array[7]=3

aux_array[a[j]] = aux_array[a[j]] - 1;
aux_array[a[8]] = aux_array[a[8]]-1;
aux_array[3] = aux_array[3]-1;
aux_array[3] = 7-1 = 6

For j=7
a[1...8]=2 5 3 0 2 3 0 3
aux_array[0...5] = 2 2 4 6 7 8

sorted_array[aux_array[a[j]]] = a[j];
sorted_array[aux_array[a[7]]]
i.e sorted_array[aux_array[0]]
i.e sorted_array[2]=0

aux_array[a[j]] = aux_array[a[j]] - 1;
aux_array[a[7]] = aux_array[a[7]]-1;
aux_array[0] = aux_array[0]-1;
aux_array[0] = 2-1 = 1

For j=6
a[1...8]=2 5 3 0 2 3 0 3
aux_array[0...5] = 1 2 4 6 7 8

sorted_array[aux_array[a[j]]] = a[j];
sorted_array[aux_array[a[6]]]
i.e sorted_array[aux_array[3]]
i.e sorted_array[6]=3

aux_array[a[j]] = aux_array[a[j]] - 1;
aux_array[a[6]] = aux_array[a[6]]-1;
aux_array[3] = aux_array[3]-1;
aux_array[3] = 6-1 = 5

For j=5
a[1...8]=2 5 3 0 2 3 0 3
aux_array[0...5] = 1 2 4 5 7 8

sorted_array[aux_array[a[j]]] = a[j];
sorted_array[aux_array[a[5]]]
i.e sorted_array[aux_array[2]]
i.e sorted_array[4]=2

aux_array[a[j]] = aux_array[a[j]] - 1;
aux_array[a[5]] = aux_array[a[5]]-1;
aux_array[2] = aux_array[2]-1;
aux_array[2] = 4-1 = 3

We have aux_array[0...5] = 1 2 3 5 7 8

Till now we have found :

sorted_array[2]=0
sorted_array[4]=2
sorted_array[6]=3
sorted_array[7]=3

Similarly follow the above step till j=1 and you will get elements in ascending order in sorted_array :

sorted_array[1]=0
sorted_array[2]=0
sorted_array[3]=2
sorted_array[4]=2
sorted_array[5]=3
sorted_array[6]=3
sorted_array[7]=3
sorted_array[8]=5

Hope this explanation is helpful to you..

Anonymous

Check this:

#include
void counting_sort(int a[],int n,int max)
{
int count[50]={0},i,j;
for(i=0;imax)
{
max=a[i];
}
}
counting_sort(a,n,max);
return 0;
}
/*4 14 8 0 2 5 2 1 0 22*/