Counting Sort

Problem

Counting Sort is a non-comparison-based sorting algorithm that works well when there is a limited range of input values. It counts the number of occurrences of each element and uses this information to place elements in their correct sorted positions.

Examples:

Example 1:
Input: arr = [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: The algorithm counts the occurrences of each element and places them in their correct sorted positions.

Example 2:
Input: arr = [5, 2, 9, 5, 2, 3, 5]
Output: [2, 2, 3, 5, 5, 5, 9]
Explanation: The algorithm efficiently sorts the array by counting the occurrences of each element.

Solution

Intuition

  • Counting Sort is efficient when the range of input values is not significantly larger than the number of elements to be sorted.
  • It works by counting the occurrences of each distinct element in the input array.
  • Then, it calculates the position of each element in the output array based on these counts.
  • Unlike comparison-based sorting algorithms, Counting Sort has a linear time complexity when the range of input values is fixed.

Approach

  • Find the range of input values (minimum to maximum).
  • Create a count array to store the count of each unique element.
  • Modify the count array such that each element at each index stores the sum of previous counts (cumulative count).
  • Build the output array by placing each element at its correct position based on the count array.
  • Copy the output array back to the original array (if needed).

Complexity Analysis

  • Time Complexity: O(n + k) where n is the number of elements and k is the range of input values.
  • Space Complexity: O(n + k) for the output array and the count array.
Implementation
CPP
Run your code to see output here