Counting sort

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.

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.


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

Nothing much.. just a simple implementation of the Counting Sort. Time

Complexity is O(n) and space complexity is O(n+m).

Counting Sort in java

package sorting;

/**
 *

 * Implements a count sort with O(n) time complexity
 *
 */
public class CountSort {

 int[] countArray=null;
 int[] resultArray=null;

 public int[] sort(int[] inputArray,int maxNumber){
  //countArray - Actually this should be length of the max number in inputArray
  countArray=new int[maxNumber+1]; 
  resultArray=new int[inputArray.length];

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

  for(int i=0;i<resultArray.length;i++){
   resultArray[i]=0;
  }

  //Find frequency of occurrence and store in countArray as (index,count)
  for(int j=0;j<inputArray.length;j++){
   countArray[inputArray[j]]=countArray[inputArray[j]]+1;
  }

  //Assign partial sums to each index of countArray
  //System.out.println("Number of values smaller than "+0+"="+countArray[0]);
  System.out.println("Partial Sums:");
  int k=0;
  for(k=1;k=1;k-–){
   System.out.println(“Index=”+(countArray[inputArray[kk-1]]-1)+” value=”+inputArray[kk-1]);
   resultArray[countArray[inputArray[kk-1]]-1]=inputArray[kk-1];
   –countArray[inputArray[kk-1]]; //This is to make sure duplicates are sorted in order
  }
    // Change countArray[i] so that countArray[i] now contains actual position of
    // this character in resultArray array
    for (i = 1; i <= maxNumber; ++i)
        countArray[i] += countArray[i-1];
 
    // Build the resultArray character array
    for (i = 0; inputArray[i]; ++i)
    {
        resultArray[countArray[inputArray[i]]-1] = inputArray[i];
        --countArray[inputArray[i]];
    }
 
    
  return resultArray;
 }

 public static void main(String[] a){

  CountSort cs=new CountSort();
  int[] sortedArray=cs.sort(new int[]{2,5,3,0,2,3,0,3},5);
  //int[] sortedArray=cs.sort(new int[]{1,3,2,0,4,5,7,6},7);
  System.out.println(“\n\nResultant Array values visited in Order:”);
  for(int val:sortedArray){
   System.out.print(val+” “);
  }

 }

}

Output:
Partial Sums:
Number of values smaller than 0=2
Number of values smaller than 1=2
Number of values smaller than 2=4
Number of values smaller than 3=7
Number of values smaller than 4=7
Number of values smaller than 5=8
Resultant Array Index Vs Values:
Index=6 value=3
Index=1 value=0
Index=5 value=3
Index=3 value=2
Index=0 value=0
Index=4 value=3
Index=7 value=5
Index=2 value=2
Resultant Array values visited in Order:
0 0 2 2 3 3 3 5