Counting Sort Implementation in Python

Counting sort is a sorting algorithm that works by counting the number of occurrences of each unique element in the input array and using that count to place each element in its correct position in the output array. It is a linear time complexity algorithm and has a worst-case time complexity of O(n+k), where n is the size of the input array and k is the range of the input values.

How the Algorithm Works

The algorithm works by first counting the number of occurrences of each unique element in the input array. This is done by creating a count array, where each index corresponds to a unique element in the input array, and the value at that index represents the number of occurrences of that element.

Once the count array is created, a prefix sum array is generated by taking the cumulative sum of the count array. This prefix sum array gives the starting index for each element in the sorted array.

Finally, the sorted array is generated by iterating over the input array and placing each element in its correct position in the output array based on the prefix sum array.

Algorithm Implementation

Here is the implementation of counting sort in Python:

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for i in arr:
        count[i] += 1
    prefix_sum = [count[0]]
    for i in range(1, max_val + 1):
        prefix_sum.append(prefix_sum[-1] + count[i])
    output = [0] * len(arr)
    for i in arr:
        output[prefix_sum[i] - 1] = i
        prefix_sum[i] -= 1
    return output

Let’s go through this implementation step-by-step:

• The first step is to find the maximum value in the input array. This is done using the built-in max() function in Python.
• Next, we create a count array of size max_val + 1, where each index corresponds to a unique element in the input array, and initialize all elements to 0.
• We then count the number of occurrences of each element in the input array by iterating over the array and incrementing the count array at the index corresponding to the current element.
• Next, we generate a prefix sum array by taking the cumulative sum of the count array. This is done by iterating over the count array and appending the sum of the current element and the previous element in the prefix sum array.
• Finally, we generate the sorted array by iterating over the input array and placing each element in its correct position in the output array based on the prefix sum array. This is done by first decrementing the value at the index corresponding to the current element in the prefix sum array, and then placing the current element in the output array at the index given by the decremented value in the prefix sum array.

Time and Space Complexity

Counting sort has a linear time complexity of O(n + k), where n is the size of the input array and k is the range of the input values. This is because the algorithm makes use of the count array, which allows for constant time access to the number of occurrences of each element in the input array.

The space complexity of counting sort is also O(n + k), as it requires the creation of the count array and prefix sum array, which each have a size of k+1, as well as the output array which has a size of n.

Example Run

Let’s run an example of counting sort to see how it works:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = counting_sort(arr)
print(sorted_arr)

The output of this code should be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Here, we have an input array of length 11 with a range of values from 1 to 9. The algorithm first generates a count array with the number of occurrences of each element in the input array:

count = [0, 2, 1, 2, 1, 3, 0, 0, 1, 1]

Then, a prefix sum array is generated from the count array:

prefix_sum = [0, 2, 3, 5, 7, 10, 10, 10, 11, 12]

Finally, the sorted array is generated by iterating over the input array and placing each element in its correct position in the output array based on the prefix sum array:

output = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in arr:
    output[prefix_sum[i] - 1] = i
    prefix_sum[i] -= 1

The final output array is:

output = [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Conclusion

Counting sort is a simple and efficient sorting algorithm that has a linear time complexity and can be used for sorting arrays with a small range of input values. Its implementation in Python is straightforward and can be easily adapted for use in various applications.