COUNTING SORT PROGRAM IN C

COUNTING SORT PROGRAM IN C

COUNTING SORT

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

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