Counting Sort

What You’ll Learn 📚

• Understanding the core concepts of Counting Sort
• Key terminology and definitions
• Step-by-step examples from simple to complex
• Common questions and troubleshooting tips
• Practical exercises to reinforce learning

Introduction to Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each unique element in the input data. It’s particularly efficient when the range of input values is not significantly larger than the number of elements to be sorted. Unlike other sorting algorithms, Counting Sort doesn’t compare elements directly, making it unique and efficient for certain types of data.

Key Terminology

• Non-comparison-based: A sorting method that doesn’t compare elements directly.
• Range: The difference between the maximum and minimum values in the input data.
• Stable Sort: Maintains the relative order of equal elements.

Simple Example

def counting_sort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m                # Initialize count array
    for a in arr:
        count[a] += 1             # Count each element
    i = 0
    for a in range(m):
        for _ in range(count[a]):
            arr[i] = a            # Place elements back into array
            i += 1
    return arr

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))

Progressively Complex Examples

Example 1: Handling Larger Ranges

def counting_sort_large_range(arr):
    min_val = min(arr)
    max_val = max(arr)
    range_of_elements = max_val - min_val + 1
    count = [0] * range_of_elements
    output = [0] * len(arr)

    for i in range(0, len(arr)):
        count[arr[i] - min_val] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1

    for i in range(0, len(arr)):
        arr[i] = output[i]

    return arr

# Example usage
arr = [10, -5, 0, 3, 7, 3, -2]
print(counting_sort_large_range(arr))

Example 2: Counting Sort with Objects

class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade

    def __repr__(self):
        return f"{self.name}: {self.grade}"

students = [Student("Alice", 3), Student("Bob", 2), Student("Charlie", 3)]

# Sort students by grade using counting sort
sorted_students = counting_sort_large_range([s.grade for s in students])
print(sorted_students)

Common Questions and Answers

1. Why is Counting Sort efficient?

   Counting Sort is efficient for small ranges of integers because it doesn’t involve comparison operations, which can be time-consuming.

2. Can Counting Sort handle negative numbers?

   Yes, by adjusting the range calculation to account for negative values, Counting Sort can handle them effectively.

3. Is Counting Sort stable?

   Yes, Counting Sort is stable, meaning it preserves the relative order of equal elements.

4. What is the time complexity of Counting Sort?

   The time complexity is O(n + k), where n is the number of elements and k is the range of the input.

5. When should I use Counting Sort?

   Use Counting Sort when the range of input values is not significantly larger than the number of elements to be sorted.

Troubleshooting Common Issues

Ensure your count array is initialized correctly to avoid index errors.

If your output isn’t as expected, double-check your range calculations, especially with negative numbers.

Practice Exercises

1. Implement Counting Sort for an array of floating-point numbers by scaling them to integers.
2. Modify the Counting Sort algorithm to sort an array of strings based on their lengths.

For further reading, check out the Counting Sort Wikipedia page and the GeeksforGeeks tutorial.