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

Share this

Related Posts

Previous
Next Post »

3 comments

comments
11 April 2015 at 11:14 delete

// 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;
}
i can't understand this please help me..

Reply
avatar
12 April 2015 at 09:55 delete

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

Reply
avatar
Anonymous
5 February 2016 at 12:23 delete

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

Reply
avatar