Category Archives: Counting Sort

How does a counting sort work?

Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given.

Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.

For example let us assume the range of numbers is 0-4. and we have an input array as follows.


3
0
3
2
4
0
2
1
2
4

This is basically integer sorting algorithm where in 
  1. The first iteration it counts the frequency of each number appearing the list. These counts are stored in an array indexed by the numbers itself. 
  2. In the second iteration, it counts the prefix sum array by counting how many numbers that are less than or equal to that number.
  3. The third iteration places the numbers in the correct place based on their frequency.
Count array


Index
0
1
2
3
4
Counts
2
1
3
2
2
Prefix Sum
2
3
6
8
10

  

 You can take a look at this animation for understanding counting sort better.

The following Java program implements the above approach.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/10/13
* Time: 5:29 AM
* To change this template use File | Settings | File Templates.
*/
public class CountingSortDemo {
public static void main(String[] args)
{
int[] numArray = {3,0,5,9,6,2,4,5,4,1};
int[] sortedArray = countingSort( numArray );
for( int i = 0; i < sortedArray.length; i++ )
{
System.out.print( sortedArray[i] + " ");
}
}
//Counting sort method
public static int[] countingSort(int [] array )
{
int[] sortedArray = new int[array.length];
int[] countArray = new int[10]; //For simplicity Assume the range 0-9
int i;
for( i = 0; i < array.length; i++ )
{
countArray[ array[i] ]++;
}
//calculate the prefix sums
for( i = 1; i < countArray.length; i++ )
{
countArray[i] += countArray[i-1];
}
//place the elements in the sorted array
for( i = 0; i < array.length; i++ )
{ 
            //Get the index to place into sorted array 
            int cIndex = countArray[ array[i] ];

sortedArray[cIndex-1] = array[i];
//decrement the frequency so that the same number is placed next
            //to previous entry 
countArray[ array[i] ]--;
}
return sortedArray;
}

}

This code is generic to sort any array objects with integer keys. If we just want to sort the array, we can combine the last two loops where we can fill the array with count of each number in order. You can do this by the following loop. 

int resIndex = 0;
for( i = 0; i < countArray.length; i++ )
{
for( int j = 0; j < countArray[i]; j++)
sortedArray[resIndex++] = i;
}