Counting Sort

Counting Sort Algorithm

All the algorithms we have learned so far (Bubble, Selection, Insertion, Quick) are Comparison Sorts. They work by constantly asking: "Is number A bigger than number B?"

Counting Sort does something completely different. It doesn't compare elements at all!

1. How Does Counting Sort Work?

Counting Sort works by keeping a tally of how many times each number appears in the array.

Real-Life Analogy

Imagine you have a big bucket of red, blue, and green balls. You want to line them up in order: all red, then all blue, then all green.

Instead of comparing balls to each other, you just count them:

• Red: 4
• Blue: 2
• Green: 3

Now, you just place 4 red balls in a row, followed by 2 blue balls, followed by 3 green balls. You are done! That is exactly how Counting Sort works with numbers.

2. The Step-by-Step Process

Let's say we want to sort this array: [4, 2, 2, 5, 3, 3]

Step 1: Find the Maximum Value The largest number in our array is 5.

Step 2: Create a Count Array We create a new array filled with zeros, from index 0 up to our max value 5. [0, 0, 0, 0, 0, 0] (These represent the counts for numbers 0, 1, 2, 3, 4, 5).

Step 3: Count the Frequencies We look at our original array and tally up the numbers.

• We have zero 0s and zero 1s.
• We have two 2s.
• We have two 3s.
• We have one 4.
• We have one 5.

Our Count Array now looks like this: Index: [ 0, 1, 2, 3, 4, 5 ] Count: [ 0, 0, 2, 2, 1, 1 ]

Step 4: Rebuild the Sorted Array We simply read our Count Array from left to right to build the final sorted array.

• Write 2 twice.
• Write 3 twice.
• Write 4 once.
• Write 5 once.

Final Sorted Array: [2, 2, 3, 3, 4, 5].

Counting Sort: Tallying the frequencies and writing them out in order.

3. Counting Sort Code Example

Here is a simple Python implementation of Counting Sort. Notice that there are no if arr[i] > arr[j] comparisons!

def counting_sort(arr):
    # 1. Find the maximum value to know the size of the count array
    max_val = max(arr)
    # 2. Create a count array of size max_val + 1, filled with 0s
    count = [0] * (max_val + 1)
    # 3. Store the count of each element
    for num in arr:
        count[num] += 1
    # 4. Rebuild the sorted array
    sorted_arr = []
    for i in range(len(count)):
        # Append the index 'i' to our result 'count[i]' times
        for j in range(count[i]):
            sorted_arr.append(i)
    return sorted_arr

numbers = [4, 2, 2, 5, 3, 3]
print("Original:", numbers)
print("Sorted:", counting_sort(numbers))

4. Time and Space Complexity

• Time Complexity: O(n + k). Where n is the number of elements in the input array, and k is the maximum value. It runs in linear time, which is phenomenally fast!
• Space Complexity: O(k). We have to create a new "Count Array" up to the maximum value.

The Big Weakness

Why don't we use Counting Sort for everything? Because of the Space Complexity.

If you want to sort an array like this: [2, 1, 1000000], the algorithm will create a count array with 1,000,000 empty slots just to sort three numbers! That is a massive waste of computer memory.

Therefore, Counting Sort is only useful when the range of numbers is small.