SwadhyAI Notes

All Python notes

Counting Sort in Python 🔢

Non-Comparison Sort

Counting sort is an integer sorting algorithm that operates by counting the number of objects that have each distinct key value.

💻 Implementation

python
def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

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

    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

🎮 Interactive Counting Sort Demo

Speed:
ℹ️ Ready
Input Array
Count Array (Index = Value)
Output Array

⚠️ Constraints

It is only efficient when the range of input values (k) is not significantly greater than the number of objects to be sorted (n). Complexity: O(n + k).