Counting sort

By | March 26, 2016

Counting sort

This post deals with yet another way of sorting a given array, the Counting Sort.

How to sort an array using counting sort problem statement

Given an array arr[] of n integers, we need to sort the array using the sorting technique known as counting sort. Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Sorting an array problem example :

Let the given array be 
arr[] = { 2, 5, 1, 7, 4, 6, 5, 2}
Output : { 1, 2, 2,4, 5, 5, 6, 7 }

Counting sort video explanation :

Sorting a given array using Counting sort Solution :

In this sorting method we first create a temporary array called Count which contains the count of various unique integers given in the array(If the array is an integer array). Next ,we modify the array Count such that each element at each index stores the sum of previous counts. This modified Count array holds the positions of each element of the output. We now output each object from the input sequence followed by decreasing its count by 1.

Counting sort algorithm:

  1. Create a temp array Count to save count of each different element.
  2. Modify the count array such that each element at each index stores the sum of previous counts.
  3. Output each object from the input sequence followed by decreasing its count by 1.

Counting sort algorithm explanation using example:

let the input array be arr[] = {2, 5, 1, 7, 4, 6, 5, 2}
 Step 1:
 Index : 0 1 2 3 4 5 6 7 8 9
 Count : 0 1 2 1 1 2 1 1 0 0
Step 2:
 Index : 0 1 2 3 4 5 6 7 8 9
 Count : 0 1 3 4 5 7 8 9 9 9
Step 3:
Now we process the input data 2, 5, 1, 7, 4, 6, 5, 2
1. Position of 2 is at index 3. And we decrease the count of index 2 by 1.
2. Position of 5 is 7. It is placed at position 7 in array and count is 
   decreased by 1.
3. Position of 1 is 1. The count is decreased and so on.

How to sort an array using counting sort solution code in C++:

#include <bits/stdc++.h>
using namespace std;
#define RANGE 255

/*Function to print a given array*/
void printArray(int arr[], int n)
{
 for(int i = 0;i<n; i++)
   cout<<arr[i]<<" ";
}

/*The main function that sort the given integer arr[]*/
void countSort(int arr[], int n)
{
    /* The output integer array that will have sorted arr*/
    int output[n+1];
 
    /*Create a count array to store count of inidividual
        elements and initialize count array as 0*/
    int count[RANGE + 1] = {0}, i;
    
    /* Store count of each element*/
    for(i = 0; i<n; ++i)
        ++count[arr[i]];
 
    /* Change count[i] so that count[i] now contains actual
        position of this element in output array*/
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];
 
    /* Build the output integer array*/
    for (i = 0; i<n; ++i)
    {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }
 
    /*Copy the output array to arr, so that arr now
       contains sorted integers */
    for (i = 0; i<n; ++i)
        arr[i] = output[i];
        
    cout<<"Sorted array is \n";
    printArray(arr,n);
}
 
// Driver program to test above function
int main()
{
    int arr[] = {  2, 5, 1, 7, 4, 6, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]); 
    countSort(arr,n);
    return 0;
}

 Output:

Sorted array is 
1 2 2 4 5 5 6 7

 Time Complexity:O(N+K)
Space Complexity:O(N+K)

Here K is the range of integers in the given array.

Note: This sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. It can also be extended to work for negative inputs.