Counting Sort – Sorting Algorithm

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm. It sorts integers by counting the occurrences of each value in the dataset. This algorithm is particularly efficient when dealing with small, positive integers or data that can be mapped to integers in a limited range.

---

1. How it Works

1. Define the Range: Determine the range of input data by finding the minimum and maximum values.
2. Count Occurrences: Create a count array where each index represents a number, and its value represents the frequency of that number in the input array.
3. Cumulative Count: Compute a cumulative count in the count array to determine the position of each element in the sorted output.
4. Sort: Place elements into the output array using the information from the cumulative count.
5. Copy Back: Copy the sorted output back into the original array if needed.

---

2. Characteristics

• Time Complexity: O(n + k)
  • n: Number of elements in the input array
  • k: Range of the input values (max value – min value)
• Space Complexity: O(n + k)
• Stable Sorting: Counting Sort preserves the relative order of equal elements.
• Limitations:
  • Works only for integer or integer-mappable data.
  • Becomes inefficient if the range of values (k) is significantly larger than the number of elements (n).

---

3. Example

Input Array: [4, 2, 2, 8, 3, 3, 1]

1. Count Occurrences:

   • count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
     • Each index represents a number, and its value represents its frequency.

2. Cumulative Count:

   • count array: [0, 1, 3, 5, 6, 6, 6, 6, 7]
     • This cumulative count indicates the positions of elements in the sorted output.

3. Sort:

   • Use the count array to place elements in their correct positions in the output array:
     • Output: [1, 2, 2, 3, 3, 4, 8]

---

4. Pros and Cons

Advantages:

1. Linear Time Complexity: When the range of values is small, Counting Sort is faster than comparison-based algorithms.
2. Stable Sort: Preserves the relative order of elements with equal values.

Disadvantages:

1. Space Requirement: Requires additional memory for the count array and the output array.
2. Limited Applicability: Not suitable for datasets with large ranges or non-integer data.

---

5. Java Implementation

import java.util.Arrays;
public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        // Step 1: Find the range of the array
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int range = max - min + 1;
        // Step 2: Create count array and output array
        int[] count = new int[range];
        int[] output = new int[arr.length];
        // Step 3: Count occurrences of each number
        for (int num : arr) {
            count[num - min]++;
        }
        // Step 4: Compute cumulative count
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        // Step 5: Place elements into output array in sorted order
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        // Step 6: Copy sorted array back to the original array
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original Array: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python Implementation

def counting_sort(arr):
    if not arr:
        return arr
    # Step 1: Find the range of the array
    min_val = min(arr)
    max_val = max(arr)
    range_val = max_val - min_val + 1
    # Step 2: Create count array and output array
    count = [0] * range_val
    output = [0] * len(arr)
    # Step 3: Count occurrences of each number
    for num in arr:
        count[num - min_val] += 1
    # Step 4: Compute cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    # Step 5: Place elements into output array in sorted order
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1
    return output
# Example usage
if __name__ == "__main__":
    arr = [4, 2, 2, 8, 3, 3, 1]
    print("Original Array:", arr)
    sorted_arr = counting_sort(arr)
    print("Sorted Array:", sorted_arr)

---

7. When to Use Counting Sort

1. Small Integer Ranges:

   • Sorting student grades, small datasets, or limited ranges.

2. Real-Time Systems:

   • When a predictable execution time is required.

3. Special Cases:

   • Large datasets where the range of numbers is limited.

Counting Sort is highly efficient in specific scenarios but requires careful consideration of its limitations.