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.
Consider an array with the following elements:
[4, 2, 2, 8, 3, 3, 1]
To sort this array using counting sort, follow these steps:
Let's apply these steps to the example array:
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:
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.