Counting Sort Program in Java

In this post we’ll see how to write counting sort program in Java. Counting sort is one of the O(N) sorting algorithm like Radix Sort and Bucket Sort. Since it runs in linear time (O(N)) so counting sort is faster than the comparison based algorithms like merge sort and quick sort.

Though counting sort is one of the fastest sorting algorithm but it has certain drawbacks too. One of them is that the range of elements should be known beforehand. Counting sort also needs auxiliary space as it needs to store the frequency of elements.

How does counting sort work

Counting sort works by counting the frequency of each element to create a frequency array or count array. Then these counts are used to compute the index of an element in the sorted array.

Create a count array to store the count of each element. If the range of elements is 0 to k then count array should be of length k+1. For example if max element in the array is 15 then count array should be of length 16.
Iterate through the elements in input array and for each element increment its count in the corresponding index in the count array.
For example if input array is- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]

Then the count array would be like below-
Modify the count array so that each index stores the sum of element at current index + element at previous index.
Now using this modified count array you need to construct the sorted array. For that you take an element from the input array and go to that index in the modified count array to get a value. That value is the place, of the element picked from the input array, in the sorted array.
In the count array decrement the value by 1 too.
For example if input array and modified count array are as follows-

First element in the input array is 0, so consult the 0th index in the count array which is 1. That means 0 goes at the place 1 (i.e. index 0) in the sorted array. Decrement the value in the count array too. In this step value at index 0 in the count array will be decremented by 1 so that it becomes 0.

Second element in the input array is 4, so consult the 4th index in the count array which is 4. That means 4 goes at the place 4 (i.e. index 3) in the sorted array. With in input array an element may be repeated and those should be grouped together. For that we need to decrement the value in the count array. In this step value at index 4 in the count array will be decremented by 1 so that it becomes 3.

When the next 4 is encountered in the input array value at the 4th index in the count array will be 3. That means next 4 goes at the place 3 (i.e. index 2) in the sorted array.

Counting Sort Java program

public class CountingSort {

  public static void main(String[] args) {
    int[] arr = {0, 4, 2, 6, 5, 4, 8, 9, 8, 6};
    // max element + 1
    int range = 10;
    System.out.println("Original Array- " + Arrays.toString(arr));
    arr = countingSort(arr, range);
    System.out.println("Sorted array after counting sort- " + Arrays.toString(arr));
  }
    
  private static int[] countingSort(int[] arr, int range){
    int[] output = new int[arr.length];
    int[] count = new int[range];
    //count number of times each element appear
    for(int i = 0; i < arr.length; i++){
      count[arr[i]]++;
    }
    System.out.println("Count array- " + Arrays.toString(count));
    // each element stores (sum of element at current index 
    //+ element at previous index)
    for(int i = 1; i < range; i++){
      count[i] = count[i] + count[i-1];
    }
    System.out.println("Modified count- " + Arrays.toString(count));
    for(int i = 0; i < arr.length; i++){
      output[count[arr[i]] - 1] = arr[i];
      count[arr[i]]--;
    }
    return output;
  }
}

Output

Original Array- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]
Count array- [1, 0, 1, 0, 2, 1, 2, 0, 2, 1]
Modified count- [1, 1, 2, 2, 4, 5, 7, 7, 9, 10]
Sorted array after counting sort- [0, 2, 4, 4, 5, 6, 6, 8, 8, 9]

Performance of Counting Sort

If the number of elements to be sorted is n and the range of elements is 0-k then the time complexity of Counting sort can be calculated as-

Loop to create count array takes O(n) time. Second loop where count array is modified takes O(k) time and creating sorted output array again takes O(n) time. Thus the time complexity with all these combined comes as O(2n+k). Since constants are not taken into consideration so the time complexity of Counting sort is O(n+k).

Auxiliary space requirement is also (n+k). Count array takes k space and the output array n. Thus the space complexity of Counting sort is O(n+k).

That's all for this topic Counting Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Monday, April 18, 2022