Counting Sort Algorithm

Introduction to Counting Sort

Counting sort is a non-comparative sorting algorithm that sorts integers by counting the occurrences of each unique value in the input array. The count is used to calculate the position of each element in the sorted array. Counting sort is efficient for sorting integers when the range of the numbers is known and not significantly larger than the number of elements in the array.

---

Step-by-Step Process

Consider an array with the following elements:

[4, 2, 2, 8, 3, 3, 1]

To sort this array using counting sort, follow these steps:

1. Find the Range: Determine the maximum value in the array to define the range of the count array.
2. Initialize Count Array: Create and initialize a count array with zeros, with a size equal to the range.
3. Count Elements: Iterate over the input array and increase the count for each value in the count array.
4. Accumulate Counts: Modify the count array such that each element at each index stores the sum of previous counts. This will give the positions of elements in the sorted array.
5. Sort the Array: Build the output array by placing elements at their correct positions using the count array.

Let's apply these steps to the example array:

• Input array: [4, 2, 2, 8, 3, 3, 1]
• Range: Maximum value is 8, so create a count array of size 9 (0 to 8).
• Count array after counting elements: [0, 1, 2, 2, 1, 0, 0, 0, 1]
• Count array after accumulation: [0, 1, 3, 5, 6, 6, 6, 6, 7]
• Output array after sorting: [1, 2, 2, 3, 3, 4, 8]

---

Pseudo Code for Counting Sort

Below is the pseudo code for the counting sort algorithm:

function countingSort(array, maxVal)
    count = array of size (maxVal + 1) with zeros
    output = array of size (length(array))

    for each element in array do
        count[element] += 1
    end for

    for i = 1 to maxVal do
        count[i] += count[i - 1]
    end for

    for each element in array do
        output[count[element] - 1] = element
        count[element] -= 1
    end for

    return output
end function

Explanation:

• Initialize: The function starts by creating a count array of size maxVal + 1 (to include the maximum value) and initializes it with zeros. It also creates an output array of the same size as the input array.
• Count Elements: The count array is populated with the frequency of each element from the input array.
• Accumulate Counts: The count array is modified to store the cumulative count of elements, which indicates the position of elements in the output array.
• Sort the Array: The output array is built by placing elements at their correct positions using the count array, and the count array is decremented after placing each element.

---

Python Program to Implement Counting Sort

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for num in arr:
        count[num] += 1

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

    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

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

This Python program defines a function to perform counting sort on an array. The function initializes the count array, counts the occurrences of each element, accumulates the counts, and builds the sorted output array.