Counting sort – counting sort algorithm. What? Yes! Just like that!
The algorithm involves at least two arrays, the first is a list of integers to be sorted, the second is an array of size = (maximum number – minimum number) + 1, initially containing only zeros. Next, the numbers from the first array are sorted out, the index in the second array is obtained by the element-number, which is incremented by one. After going through the entire list, we will get a completely filled second array with the number of repetitions of numbers from the first. The algorithm has a serious overhead – the second array also contains zeros for numbers that are not in the first list, the so-called. memory overhead.
After getting the second array, iterate over it and write the sorted version of the number by index, decrementing the counter to zero. Initially, the zero counter is ignored.
An unoptimized example of how the counting sort algorithm works:
- Input array 1,9,1,4,6,4,4
- Then the array to count will be 0,1,2,3,4,5,6,7,8,9 (minimum number 0, maximum 9)
- With total counters 0,2,0,0,3,0,1,0,0,1
- Total sorted array 1,1,4,4,4,6,9
Algorithm code in Python 3:
print("Counting Sort")
numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]
minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange
print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximum number: {maximal}")
print(f"Count list size: {countListRange}")
for number in numbers:
index = number - minimal
countList[index] += 1
replacingIndex = 0
for index, count in enumerate(countList):
for i in range(count):
outputNumber = minimal + index
numbers[replacingIndex] = outputNumber
replacingIndex += 1
print(numbers)Due to the use of two arrays, the time complexity of the algorithm is O(n + k)
Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort
Sources
https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC