DSA Counting Sort

Welcome to TheCodingCollege.com, where you learn the intricacies of Data Structures and Algorithms (DSA) with clarity and depth! In this post, we’ll explore Counting Sort, a non-comparison-based sorting algorithm that shines in specific use cases.

What is Counting Sort?

Counting Sort is an integer sorting algorithm that works by counting the occurrences of each element in the input array. This count information is used to determine the correct position of each element in the sorted array.

Unlike other sorting algorithms like QuickSort or Merge Sort, Counting Sort doesn’t compare elements but relies on the range of input values, making it incredibly efficient for small, discrete datasets.

How Does Counting Sort Work?

Here’s the step-by-step process:

1. Determine the Range: Identify the maximum and minimum values in the array.
2. Count Occurrences: Create a count array to store the frequency of each element.
3. Accumulate Counts: Modify the count array to determine the position of each element in the output array.
4. Build Output: Traverse the input array and place each element in its correct position based on the count array.
5. Copy Back: Copy the sorted output array back to the input array (if required).

Steps in Counting Sort

Let’s sort the array [4, 2, 2, 8, 3, 3, 1]:

Initial Array: [4, 2, 2, 8, 3, 3, 1].

1. Find Range:
   • Maximum = 8
   • Minimum = 1
   • Range = 8 – 1 + 1 = 8
2. Count Occurrences:
   • Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1].
3. Accumulate Counts:
   • Cumulative count: [0, 1, 3, 5, 6, 6, 6, 6, 7].
4. Place Elements in Output Array:
   • Output array: [1, 2, 2, 3, 3, 4, 8].
5. Final Sorted Array: [1, 2, 2, 3, 3, 4, 8].

Counting Sort Code Implementation

Python Code:

def counting_sort(arr):
    # Find the maximum and minimum values
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    # Initialize count array
    count = [0] * range_val

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

    # Modify count array to store positions
    for i in range(1, range_val):
        count[i] += count[i - 1]

    # Build the output array
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

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

# Example usage
array = [4, 2, 2, 8, 3, 3, 1]
counting_sort(array)
print("Sorted Array:", array)

Output:

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

Java Code:

import java.util.Arrays;

class CountingSort {
    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]++;
        }

        // Modify count array to store positions
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

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

        // Copy output to 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};
        countingSort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

Time and Space Complexity

Advantages and Disadvantages of Counting Sort

Advantages

1. Linear Time: Faster than comparison-based algorithms for small ranges.
2. Stable Sorting: Maintains the relative order of equal elements.
3. Non-Comparison-Based: Ideal for integers and small datasets.

Disadvantages

1. Range Dependency: Performance degrades with a large range of values.
2. Not In-Place: Requires additional space for the count and output arrays.
3. Limited Applicability: Doesn’t work for floating-point numbers or non-discrete data.

Applications of Counting Sort

1. Histogram Counting: Analyzing frequency distributions.
2. Sorting Fixed Ranges: Useful for sorting grades, ages, or other constrained data.
3. Digit-Based Sorting: Forms the basis for Radix Sort.

Comparison with Other Sorting Algorithms

Conclusion

Counting Sort is a powerful algorithm for sorting integers within a limited range efficiently. While it has its limitations, its speed and stability make it a valuable tool in the DSA toolkit.

Learn more about sorting algorithms and DSA concepts at TheCodingCollege.com and enhance your programming expertise!