Counting Sort Java Program

This tutorial shows how to write Counting sort program in Java. Counting sort is an integer sort algorithm. It is different from other comparison based algorithms like merge sort, selection sort as it doesn’t sort by comparing values. In counting sort, frequency of each element is counted and using it final position of each element is calculated.

One of the restriction while using Counting sort is that range of elements (maximum element) has to be known. Counting sort also needs extra space for storing frequency of elements.

Counting Sort Algorithm

1- In counting sort initially you need to count the frequency of each element and keep that in count array. So first thing is to create a count array. Length of the count array is calculated as– Max element in the input array + 1. For example if the maximum element in the input array is 10 then length of count array is 11.

2- Each index in the count array maps to element 0 to max element in input array. So increment the count at the corresponding index in the count array for each element in the input array. That way you get the frequency of each element. For example if array is- [1, 3, 2, 6, 2, 5, 8, 7, 8, 6]

Then count array is-

3- To get the actual position of the element in the sorted output array you need to modify the count array. Each index in the count array should store the sum of all the elements till that index. You can get that using the formula– count[i] = count[i] + count[i-1].

Thus for our example modified count array is- [0, 1, 3, 4, 4, 5, 7, 8, 10]

4- Using this modified count array you need to get the position of each element in the output sorted array. To get the final position take an element from an input array and get the value at that index in the modified count array. That value is the final position of the element in the output array. In the modified count array decrement count at that index by 1.

Following image shows the mapping between the elements in the input array and the count array.

For example, first element in the input array is 1 so check the index 1 in the count array where the value is 1. Which means 1 should be at place 1 (index 0) in the output array. Decrement the value at index 1 in count array.

Second element in the input array is 3 so check the index 3 in the count array where the value is 4. Which means 3 should be at place 4 (index 3) in the output array. Decrement the value at index 3 in count array.

In the image you can see for some of the elements more than one element is mapping to same index. That is why count is decremented in the count array so that next time we have the correct value.

Take the example of third element in input array which is 2 so check the index 2 in the count array where the value is 3. Which means 2 should be at place 3 (index 2) in the output array. Decrement the value at index 2 in count array, now the value at index 2 is 3 -1 = 2.

Next time element 2 is encountered in the input array it will get value 2 at index 2 in the count array. So another 2 should be at place 2 (index 1) in the output array.

Ultimately we get the sorted array as- [1, 2, 2, 3, 5, 6, 6, 7, 8, 8]

Counting Sort Java program

public class CountingSort {
  public static void main(String[] args) {
    int[] arr = {10, 5, 15, 6, 12, 5, 8, 9, 0, 10, 1, 7};
    // Find the maximum element in the input array
    int max = findMaxElement(arr);
    System.out.println("Max Value in input array-" + max);
    System.out.println("Original Array- " + Arrays.toString(arr));
    int[] sortedArr = countingSort(arr, max+1);
    System.out.println("Sorted array after counting sort- " + Arrays.toString(sortedArr));
  }
	
  private static int findMaxElement(int[] arr) {
    int max = arr[0];
    for(int val : arr) {
      if (val > max)
        max = val;
    }
    return max;
  }
	
  private static int[] countingSort(int[] arr, int range){
    int[] result = new int[arr.length];
    int[] count = new int[range];
    //Calculate frequency of each element, put it in count array
    for(int i = 0; i < arr.length; i++){
        count[arr[i]]++;
    }
    System.out.println("Count array- " + Arrays.toString(count));
    
    // Modify count array to get the final position of elements
    for(int i = 1; i < range; i++){
        count[i] = count[i] + count[i-1];
    }
    System.out.println("Modified count array- " + Arrays.toString(count));
    
    // Add elements to output sorted array 
    for(int i = 0; i < arr.length; i++){
      result[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    return result;
  }
}

Output

Max Value in input array-15
Original Array- [10, 5, 15, 6, 12, 5, 8, 9, 0, 10, 1, 7]
Count array- [1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 2, 0, 1, 0, 0, 1]
Modified count array- [1, 2, 2, 2, 2, 4, 5, 6, 7, 8, 10, 10, 11, 11, 11, 12]
Sorted array after counting sort- [0, 1, 5, 5, 6, 7, 8, 9, 10, 10, 12, 15]

Counting sort time and space complexity

If the number of elements to be sorted is N and the range of elements is 0 to K then the first loop iterates the input array to get the count array i.e O(n). Count array is modified to get the final position that step has the complexity O(k). Third loop again iterate the input array so the time complexity of that step is O(n). Which adds up to O(2n + k) or you can say time complexity of Counting sort is O(n+k) as constants are not counted in Big O notation.

Count array takes k space and the output array's length is same as input array i.e. N. Thus the space complexity of counting sort is O(n+k).

That's all for the topic Counting Sort Java Program. If something is missing or you have something to share about the topic please write a comment.

You may also like

KnpCode

April 7, 2022

Counting Sort Java Program

Counting Sort Algorithm

Counting Sort Java program

Counting sort time and space complexity

No comments:

Post a Comment