Counting Sort

Counting Sort

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Counting Sort is a non-comparison-based sorting algorithm that works efficiently when the range of input values is known and relatively small. It counts the occurrences of each value in the input array and uses this information to place elements directly into their correct positions in the output array. It’s particularly effective for integers or objects that can be mapped to integers within a limited range.

Pseudocode for Counting Sort

CountingSort(arr, n, k):
    // Input: array arr of size n, elements in range [0, k]
    // Output: sorted array

    // Step 1: Initialize count array
    count = array of size k+1 initialized to 0

    // Step 2: Count occurrences of each element
    for i from 0 to n-1:
        count[arr[i]] = count[arr[i]] + 1

    // Step 3: Compute cumulative counts
    for i from 1 to k:
        count[i] = count[i] + count[i-1]

    // Step 4: Build output array
    output = array of size n
    for i from n-1 down to 0:
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] = count[arr[i]] - 1

    return output

Example

Consider the array: [4, 2, 2, 8, 3, 3, 1]

Assume the elements are integers in the range [0, 8], so k = 8.

Step-by-Step Process

1. Initialize Count Array:

   • Create count = [0, 0, 0, 0, 0, 0, 0, 0, 0] (size k+1 = 9 for values 0 to 8).

2. Count Occurrences:

   • For each element in arr, increment the corresponding index in count:
     • arr[0] = 4: count[4] += 1 → count = [0, 0, 0, 0, 1, 0, 0, 0, 0]
     • arr[1] = 2: count[2] += 1 → count = [0, 0, 1, 0, 1, 0, 0, 0, 0]
     • arr[2] = 2: count[2] += 1 → count = [0, 0, 2, 0, 1, 0, 0, 0, 0]
     • arr[3] = 8: count[8] += 1 → count = [0, 0, 2, 0, 1, 0, 0, 0, 1]
     • arr[4] = 3: count[3] += 1 → count = [0, 0, 2, 1, 1, 0, 0, 0, 1]
     • arr[5] = 3: count[3] += 1 → count = [0, 0, 2, 2, 1, 0, 0, 0, 1]
     • arr[6] = 1: count[1] += 1 → count = [0, 1, 2, 2, 1, 0, 0, 0, 1]

3. Compute Cumulative Counts:

   • Update count so each index stores the sum of counts up to that index:
     • count[0] = 0
     • count[1] = 0 + 1 = 1
     • count[2] = 1 + 2 = 3
     • count[3] = 3 + 2 = 5
     • count[4] = 5 + 1 = 6
     • count[5] = 6 + 0 = 6
     • count[6] = 6 + 0 = 6
     • count[7] = 6 + 0 = 6
     • count[8] = 6 + 1 = 7
   • Result: count = [0, 1, 3, 5, 6, 6, 6, 6, 7]
   • This indicates where each value should be placed in the output array.

4. Build Output Array:

   • Initialize output = [_, _, _, _, _, _, _] (size n = 7).
   • Process arr from right to left:
     • arr[6] = 1: count[1] = 1, place 1 at output[0], decrement count[1] to 0.
     • arr[5] = 3: count[3] = 5, place 3 at output[4], decrement count[3] to 4.
     • arr[4] = 3: count[3] = 4, place 3 at output[3], decrement count[3] to 3.
     • arr[3] = 8: count[8] = 7, place 8 at output[6], decrement count[8] to 6.
     • arr[2] = 2: count[2] = 3, place 2 at output[2], decrement count[2] to 2.
     • arr[1] = 2: count[2] = 2, place 2 at output[1], decrement count[2] to 1.
     • arr[0] = 4: count[4] = 6, place 4 at output[5], decrement count[4] to 5.
   • Resulting output = [1, 2, 2, 3, 3, 4, 8].

5. Sorted Array: [1, 2, 2, 3, 3, 4, 8]

Complexity analysis

• Time Complexity:
  • O(n + k), where n is the number of elements and k is the range of input values (max value + 1).
  • Efficient when k is not significantly larger than n.
• Space Complexity: O(n + k) for the output and count arrays.
• Stability: Stable (maintains relative order of equal elements) if implemented as shown.
• Advantages: Extremely fast for small ranges of integers, stable, and linear time when k is small.
• Disadvantages: Requires extra space, only works for non-negative integers or mappable values, inefficient if k is very large.

Notes

• Counting Sort is often used as a subroutine in Radix Sort to handle digits of integers.
• If the input includes negative numbers or non-integers, preprocess them (e.g., shift negative numbers by adding the minimum value or map to integers).
• The algorithm assumes the range of values (k) is known in advance.