Python Counting Sort

Python Counting Sort

Counting Sort is a unique sorting algorithm that is not comparison-based. Instead of comparing elements, it works by counting the number of objects that have each distinct key value. It is only effective when the range of potential items in the input list is not significantly greater than the number of items.

It is an integer sorting algorithm, meaning it's used for sorting integers.

How Counting Sort Works

1. Find the Range: First, find the maximum element in the list to determine the range of numbers we need to count (from 0 to max).
2. Create a Count Array: Create a "count" array (or hash map) of size max + 1 and initialize all its elements to 0. This array will store the count of each unique element.
3. Store Counts: Iterate through the input list. For each element, increment its corresponding counter in the count array. For example, if you see the number 3 three times, count[3] will be 3.
4. Store Cumulative Counts: Modify the count array such that each element at each index stores the sum of previous counts. This tells you the final position of each element in the sorted output.
5. Build the Output Array: Iterate through the input list in reverse. For each element, find its position in the output array using the cumulative count array, place the element, and decrement the count.

Implementing Counting Sort in Python

Here is a function that implements the counting sort algorithm.

def counting_sort(data):
    n = len(data)
    // The output array that will have sorted data
    output = [0] * n
    // Find the maximum element in the input array
    max_val = max(data)
    // Create a count array to store count of individual elements
    // and initialize count array as 0
    count = [0] * (max_val + 1)
    // Store count of each character
    for i in range(n):
        count[data[i]] += 1
    // Change count[i] so that count[i] now contains actual
    // position of this element in output array
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]
    // Build the output character array
    i = n - 1
    while i >= 0:
        output[count[data[i]] - 1] = data[i]
        count[data[i]] -= 1
        i -= 1
    // Copy the output array to data, so that data now
    // contains sorted characters
    for i in range(n):
        data[i] = output[i]

// --- Usage ---
my_list = [4, 2, 2, 8, 3, 3, 1]
counting_sort(my_list)
print("Sorted list is:", my_list)

Time and Space Complexity

Let n be the number of elements and k be the range of the input (max_val).

• Time Complexity: O(n + k). This is a linear time algorithm, which is faster than comparison-based sorts like Merge Sort (O(n log n)) when k is not significantly larger than n.
• Space Complexity: O(k) to store the count array.