Counting Sort

Counting sort is a sorting algorithm that works well when the range of the input is known and there is a limited range of input values. It is optimal when the range of the input values is small as compared to the number of elements to be sorted. 

Basic idea of counting sort is to count the number of occurrences of each unique element in the input array and use this information to determine its position in the sorted array. 

Algorithm with Dry run

Let’s take an example of the input array

Step 1 : Find the maximum element in the input array.

Here, the maximum element will be 8.

Step 2: Create an auxiliary array of size maximum+1 to store the frequency count of the elements in the input array. Initialize all the elements in the auxiliary array to 0.

Here, maximum+1 = 9. Hence, 

Step 3: Store the frequency count of each element in the auxiliary array at their respective index. For example if the count of the element 3 is 2 then store the value 2 at the 3rd index of the auxiliary array.

Hence, the auxiliary array will look like the following: 

Step 4: Store the cumulative sum of the elements of the auxiliary array

Cumulative sum is addition of all the elements upto the current element. Hence, the cumulative sum of the above example will look like : 

Step 5: Create an output array of the size of the input array. Traverse the input array to calculate the appropriate position of the elements. The appropriate element of the element is the cumulative sum of that element - 1.

Step 6: After placing each element at its correct position decrease its count in the auxiliary array by 1.

Complexity

• Time Complexity: O(N+K), 

• Space Complexity: O(K)

N = size of the input array, K = Maximum element.   

Code

#Java Code

import java.util.Arrays;

class CountingSort {

  void countingSort(int[] array, int size) {
    int[] output = new int[size];
    
    // Find the maximum element in the array
    int maxElement = Arrays.stream(array).max().orElse(0);

    // Initialize count array with all zeros
    int[] count = new int[maxElement + 1];

    // Store the count of each element
    for (int i = 0; i < size; i++) {
      count[array[i]]++;
    }

    // Store the cumulative count of each element
    for (int i = 1; i <= maxElement; i++) {
      count[i] += count[i - 1];
    }

    // Find the index of each element in the original array in the count array,
    // and place the elements in the output array
    for (int i = size - 1; i >= 0; i--) {
      output[count[array[i]] - 1] = array[i];
      count[array[i]]--;
    }

    // Copy the sorted elements back to the original array
    System.arraycopy(output, 0, array, 0, size);
  }

  // Driver code
  public static void main(String args[]) {
    int[] data = {4, 2, 2, 8, 3, 3, 1};
    int size = data.length;
    
    CountingSort countingSort = new CountingSort();
    countingSort.countingSort(data, size);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

Output

Sorted Array in Ascending Order: 
[1, 2, 2, 3, 3, 4, 8]