Counting Sort
A non-comparison sorting algorithm that operates by counting the number of objects that have each distinct key value.
Visualization
Details
Analogy
Imagine you have a big jar of colored marbles (e.g., red, blue, green). To sort them, you get separate bins for each color. You go through the marbles one by one, putting each into its corresponding color bin. This counts how many of each color you have. Finally, you just empty the bins in order (all reds, then all blues, etc.) to get a sorted collection.
Purpose
To sort an array of elements efficiently when the elements are integers within a specific, relatively small range.
Use Cases
Effective for sorting integers with a limited range. Used as a subroutine in Radix Sort. Not a general-purpose sort because it's not efficient for large ranges of values.
Algorithm Steps
find max value in arr
create count array of size max+1
for each element in arr:
count[element]++
for i = 1 to max:
count[i] += count[i-1]
create output array
for i = n-1 to 0:
output[count[arr[i]]-1] = arr[i]
count[arr[i]]--
copy output to arr
Explanation
What's Happening?
Initial unsorted array. The maximum value is 8.
Code Implementation
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
output = [0] * len(arr)
for i in arr:
count[i] += 1
for i in range(1, max_val + 1):
count[i] += count[i - 1]
for i in range(len(arr) - 1, -1, -1):
output[count[arr[i]] - 1] = arr[i]
count[arr[i]] -= 1
return output