Counting Sort

Counting Sort is a well-known sorting algorithm in computer science. It’s an integer sorting algorithm, unlike comparison-based algorithms like Quick Sort or Merge Sort.

Here’s a quick overview of how Counting Sort works:

Find the Range: Determine the range of input values (minimum and maximum values).
Count the Occurrences: Create a counting array of size equal to the range, and initialize all elements to 0. Then, iterate through the input array and increment the count of each value in the counting array.
Calculate the Cumulative Count: Modify the counting array by storing the cumulative count of occurrences. This step helps determine the position of each element in the sorted array.
Build the Sorted Array: Iterate through the input array, and for each value, place it in the sorted array at the position indicated by the cumulative count in the counting array. Decrement the count in the counting array for that value.
Copy Back to Original Array: Copy the sorted values back to the original input array if necessary.

Key Properties

Stable: If implemented correctly, it maintains the relative order of equal elements.
Not Comparison-Based: It doesn’t compare elements against each other, unlike most other sorting algorithms.
Time Complexity: O(n + k), where n is the number of elements, and k is the range of input values.
Space Complexity: O(k) for the counting array.

Limitations

It can only sort integers (or objects that can be mapped to integers).
It may not be efficient if the range of input values (k) is much larger than the number of elements (n), as it requires space proportional to the range.

Counting Sort is often used as a subroutine in other sorting algorithms like Radix Sort, and it’s particularly effective when dealing with a small range of integer values.

Description

Counting Sort is a non-comparative integer sorting algorithm. Unlike comparison-based sorting algorithms like Quick Sort, Counting Sort sorts integers within a specific range. It works by counting the occurrences of each value in the input array, then using that count to place each value in its correct position in the sorted array. It’s often useful when the range of integers is relatively small compared to the number of elements to be sorted.

Solution

Let’s look at the code for implementing Counting Sort in Java, C++, and Python.

Java

In Java, you can use an array to store the counts of each integer. Here’s a step-by-step guide:

Determine the minimum and maximum values in the array.
Create a counting array of size equal to the range.
Count the occurrences of each value.
Calculate the cumulative count.
Build the sorted array using the cumulative count.
Copy the sorted values back to the original array if necessary.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    int[] count = new int[range];
    int[] output = new int[arr.length];

    // Count occurrences
    for (int num : arr) {
        count[num - min]++;
    }

    // Calculate the cumulative count
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // Build the sorted array
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // Copy to original array
    System.arraycopy(output, 0, arr, 0, arr.length);
}

C++

In C++, you can use a similar approach, with vectors to handle the counting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <vector>
#include <algorithm>

void countingSort(std::vector<int>& arr) {
    int max = *std::max_element(arr.begin(), arr.end());
    int min = *std::min_element(arr.begin(), arr.end());
    int range = max - min + 1;
    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());

    // Count occurrences
    for(int num : arr) {
        count[num - min]++;
    }

    // Calculate the cumulative count
    for(int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // Build the sorted array
    for(int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // Copy to original array
    arr = output;
}

Python

Python’s higher-level syntax allows for a more concise implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def countingSort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    count = [0] * range_val
    output = [0] * len(arr)

    # Count occurrences
    for num in arr:
        count[num - min_val] += 1

    # Calculate the cumulative count
    for i in range(1, range_val):
        count[i] += count[i - 1]

    # Build the sorted array
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1

    # Copy to original array
    for i in range(len(arr)):
        arr[i] = output[i]

The code in all three languages follows a similar pattern and performs the sort in-place, meaning the original array is sorted without needing to return a new one. The time complexity in all cases is O(n + k), where n is the number of elements, and k is the range of input values. The space complexity is O(k) for the counting array.

title: Countingsort excerpt: This covers the countingsort algorithm and implementation. tags: array-frequency-counter

The O(N log N) performance can be beaten if the method used is other than comparisons to sort. Countingsort can sort in less than O(N log N) time.

Implementation

Countingsort works if the values to sort are integers that lie in a relatively small range. The frequence of items in the array is counted. The numbers are copied back into the array in order and based on their frequency multiple elements will be copied.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def countingsort(array, max)
  # Initialize the array to hold the frequency
  # to all 0s
  counts = [0] * max
  
  # Count the frequency
  for i in (0..array.size - 1)
    counts[i] = counts[i] + 1
  end
  
  # Copy the values back into the array
  index = 0
  for i in (0..max)
    # Copy the value i into the array counts[i] times
    for j in (1..counts[i])
      array[index] = i
      index = index + 1
    end
  end
  
  return array
end

The max parameter is the largest value in the array. The initial frequency of count for all numbers is initialized to zero. The frequency of every element in array is calculated and stored in the counts array. The last step is copying the values back into the original array. Each value is copied once, so it takes N steps. The elements with zero frequency is skipped.

In the worst case, if all the values are the same, so that the counts array contains mostly 0s, it takes M steps to skip over the 0 entries. The total run time is O(2 x N + M) = O(N + M). If M is relatively small compared to N, this is much smaller than the O(N log N).

Building Block

Array Frequency Counter