Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that have each distinct key value, and using arithmetic on those counts determine the positions of each key value in the output sequence.

---

Example:

For simplicity, consider the data in the range 0 to 9. Input data: 1, 4, 1, 2, 7, 5, 2 1) Take a count array to store the count of each distinct object. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 1 0 1 0 0 2) Modify the count array such that each element at each index stores the sum of previous counts. Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 4 4 5 6 6 7 7 7 The modified count array indicates the position of each object in the output sequence. 3) Output each object from the input sequence followed by decreasing its count by 1. Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2. Put data 1 at index 2 in output. Decrease count by 1 to place next data 1 at an index 1 smaller than this index.

---

Implementation using C:

#include <stdio.h> 
#include <string.h> 
#define RANGE 255 
  
void count_Sort(char arr[]) 
{ 
    // The output character array that will have sorted arr 
    char output[strlen(arr)]; 
  
    // Create a count array to store count of individual 
    // characters and initialize count array as 0 
    int count[RANGE + 1], i; 
    memset(count, 0, sizeof(count)); 
  
    // Store count of each character 
    for(i = 0; arr[i]; ++i) 
        ++count[arr[i]]; 
  
    /* Change count[i] so that count[i] now contains actual 
     position of this character in output array */
    for (i = 1; i <= RANGE; ++i) 
        count[i] += count[i-1]; 
  
    //output character array 
    for (i = 0; arr[i]; ++i) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        --count[arr[i]]; 
    }   
    // Copy the output array to arr, so that arr now 
    // contains sorted characters 
    for (i = 0; arr[i]; ++i) 
        arr[i] = output[i]; 
} 
  

int main() 
{ 
    char arr[] = "prateekchauhan"; 
  
    count_Sort(arr); 
  
    printf("Sorted character array: %s\n", arr); 
    return 0; 
}

Output:
Sorted character array: aaaceehhknprtu

---

Miscellaneous:

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.

Auxiliary Space: O(n+k)

It is not a comparison based algorithm.