Implement Counting Sort using Java + Performance Analysis

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

Lets understand Counting Sort using an example-
Suppose the input array to be sorted is- 10,13,9,15,7,13

• 1. Calculate the min and max values - In our case min=7 max=15

  	  for (int i = 1; i < arrayLength; i++)
          {
              if (arr[i] > max)
                  max = arr[i];
              if (arr[i] < min)
                  min = arr[i];
          }
  	 

• 2. Calculate the range by max-min range=15-7=8.
  Create an array count[] of size range
  
  

  	  int range = max - min + 1;
  	   int[] count = new int[range];
  

• 3. Now initialize the occurrence of each element in the count array.
  
  
  So the element 7 occurs 1 times, element 9 occurs 1, element 13 occurs 2 times and so on.
  

  for (int i = 0; i < arrayLength; i++)
              count[arr[i] - min]++;
               

• 4. Calculate the sum of the occurrences of the elements.
  
  add the count of each index by adding the count of previous index
  since count[7] first element so count is as it is 1
  sumcount[8]=count[7]+count[8]=1+0=1
  sumcount[9]=count[8]+count[9]=1+1=2
  sumcount[10]=count[9]+count[10]=2+1=3
  sumcount[11]=count[10]+count[11]=3+0=3
  sumcount[12]=count[11]+count[12]=3+0=3
  sumcount[13]=count[12]+count[13]=3+2=5
  sumcount[14]=count[13]+count[14]=5+0=5
  sumcount[15]=count[14]+count[15]=5+1=6
  
  

    for (int i = 1; i < range; i++)
              count[i] += count[i - 1];
      

• 5. Finally we arrange the elements according to the sumcount
  
  For the first element 10 in the unsorted array, the sumcount is 3 so place it in the third position in the array. Also decrease the sumcount by 1 when the element is placed in the new sorted array.
  testArray[3]=10
  Decrease the sumcount of element 10 by 1.
  sumcount[10]=3-1=2
  
  Similarly do the following for the occurence of other elements-
  testArray[5]=13 sumcount [13]=5-1=4
  testArray[2]=9 sumcount [9]=2-1=1
  testArray[6]=15 sumcount [15]=6-1=5
  testArray[1]=7 sumcount [7]=1-1=0
  testArray[4]=13 sumcount[13]=4-1=3
  
  
  

    for (int i = 0; i < range; i++)
              while (j < count[i])
                  arr[j++] = i + min;
      }  
      

The complete source code is as follows-

package com.javainuse;

import java.util.Arrays;

public class CountingSortExample {

    /** Counting Sort functionality **/
    public static void sort(int[] arr) {
        int arrayLength = arr.length;
        if (arrayLength == 0)
            return;
        /** find maximum and minimum values **/
        int max = arr[0], min = arr[0];
        for (int i = 1; i < arrayLength; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        int range = max - min + 1;

        int[] count = new int[range];
        /** initialize the occurrence of each element in the count array **/
        for (int i = 0; i < arrayLength; i++)
            count[arr[i] - min]++;
        /** calculate sum of indexes **/
        for (int i = 1; i < range; i++)
            count[i] += count[i - 1];
        /** modify original array according to the sum count **/
        int j = 0;
        for (int i = 0; i < range; i++)
            while (j < count[i])
                arr[j++] = i + min;
    }

    public static void main(String[] args) {

        int[] testArray = { 10, 13, 9, 15, 7, 13 };

        System.out.println("Elements before applying countingsort: " + Arrays.toString(testArray));

        sort(testArray);

        System.out.println("Elements after applying countingsort:  " + Arrays.toString(testArray));

    }

}

Performance Analysis of Counting sort

• Time complexity of Counting sort-
  Complexity of Counting sort for initializing the occurrence of each element in array+ Complexity for calculating sum of indexes.
  
  Complexity of

    /** initialize the occurrence of each element in the count array **/
          for (int i = 0; i < arrayLength; i++)
              count[arr[i] - min]++;
               

  +
  Complexity of

   /** calculate sum of indexes **/
          for (int i = 1; i < range; i++)
              count[i] += count[i - 1];
               

  So the time complexity will be-
  O(n)+O(k)=O(n+k)
  Where n will be the array length to be sorted and k will be the range i.e. the difference between the largest and the smallest element. So if the range is large then the time performance of counting sort will not be good.
• Space complexity of Counting sort-
  As we saw counting sort generates an array of the size range. So if suppose the range is 10000. Then these many buckets would be required. So an incredible amount of memory will need to be spent if the range is large.

Conclusion

If the user knows in advance the input sequence is a permutation of {1, 2, . . . , n}, then using Counting sort is much better as the time complexity will be linear O(n+k) better than the complexity of other sorting algorithms like merge sort which is O(n log n)
But if the user input is not known and the range may be large it is not advisable for using counting sort.

See Also
Overriding equals() in Java
Internal working of ConcurrentHashMap in Java
Image Comparison in Java
Java - PermGen space vs Heap space
Java - PermGen space vs MetaSpace
Java 8 Features
Java Miscelleneous Topics
Java Basic Topics
Java- Main Menu