Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the array, and stores these same elements in the auxiliary array. It was developed by Harold H. Seward in 1954.

Complexity table of counting sort

Complexity	Best case	Average case	Worst case
Time	? (n + k)	? (n + k)	O (n + k)
Space			O S(nk)

Where n is the number of the element, and k is the range of the input.

Algorithm of counting sort

Counting_Sort (array, size)  max ? find the largest element from the array.    define count array length [largest + 1].      for i ? 0 to max do       count[i] = 0 // initialize count array with all zeros.      for i ? 1 to size do       increase count of each number which has found in the array.      for i ? 1 to max do       count[i] = count[i] + count[i+1] // cumulative sum.      for i ? size to 1 decrease by 1 do       store the number in the output array.       decrease count[i]    done      return the output array End  

Example 1: Suppose we have the following array, which we have to sort.

5

5

4

1

8

2

2

3

Step 1: Find the largest element in the given array.             

Largest element is = 8   5 5 4 1 8 2 2 3  

Step 2: Initialize a new array, and the size of the new array is (Largest + 1).  

Step 3: Count each element in the given array, and stores the element at their respective index in the count array. For example: If 5 is assigned 2 times to the original array, then 2 will be stored at the 5th position in the count array. If 6 is assigned 0 times, then 0 will be stored at the 6th position in the count array. 

Step 4: Make the cumulative sum of the elements of the count array. This helps to place the elements in the correct index of the sorted array.  

Step 5:  This process will be implemented throughout the array.  

Counting sort program in C language:

  #include <stdio.h>   
void countingSort(int array[], int size)
 {   
int output[10];   
int max = array[0]; 
  for (int i = 1; i < size; i++) 
{    
 if (array[i] > max)      max = array[i];  
}     
int count[10];  
 for (int i = 0; i <= max; ++i)
{   
  count[i] = 0;  
 }    
 for (int i = 0; i < size; i++) 
{  
   count[array[i]]++;  
 }   
  for (int i = 1; i <= max; i++)
 {   
  count[i] += count[i - 1]; 
  }  
   for (int i = size - 1; i >= 0; i--) 
{    
 output[count[array[i]] - 1] = array[i]; 
    count[array[i]]--; 
  } 
   for (int i = 0; i < size; i++) 
{   
  array[i] = output[i]; 
  } 
}  
 // Function to print an array void printArray(int array[], int size)
 {  
 for (int i = 0; i < size; ++i)
 {  
   printf("%d  ", array[i]); 
  } 
  printf("\n"); 
}   // Driver code int main() 
{ 
  int array[] = {5, 5, 4, 1, 3, 8};
  int n = sizeof(array) / sizeof(array[0]);
   countingSort(array, n); 
  printArray(array, n); 
}