My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is:
def counting_sort(input_list, max_int):
# Make a histogram array for occurences of each integer
count = [0] * (max_int + 1)
for i in range(len(input_list)):
value = input_list[i]
count[value] += 1
# count -> [0, 2, 2, 0, 0, 1, 1, 1]
# Prefix sum the count histogram array
modified_count = [i for i in count]
for i in range(1, len(count)):
modified_count[i] = modified_count[i-1] + modified_count[i]
# modified_count -> [0, 2, 4, 4, 4, 5, 6, 7]
# Output elements from input_list according to modified_count
output = [0] * len(input_list)
for i in range(len(input_list)):
output_value = input_list[i]
output_index = modified_count[output_value] - 1
output[output_index] = output_value
modified_count[input_list[i]] -= 1
print("Output", output)
counting_sort([1,5,7,6,2,1,2], 7)
Most of this algorithm makes sense to me:
- The algorithm makes a histogram of occurrences where
count[i]
is the number of occurrences. Then we prefix sum this
count
histogram which gives usmodified_count
—an array that stores the number of items with a key less thani
.We then use that array to determine the index of the integer in the output array.
The Wikipedia article states, that the modified_count
array, which stores the number of items with a key less than i
, is the same as an array where each item is the "the first index at which an item with key i
should be stored in the output array."
That quote from Wikipedia is what I don't understand.
In a nutshell, my question is: Why is the number of items with a key less than i
the same as the first output array index for an item with key i
. It seems so clever, but very mystifying (currently).
output
array properly. I hadoutput = [0] * max_int
when I should've hadoutput = [0] * len(input_list)
so I was getting off-by-one errors. I fixed it in my repl and in the original question. $\endgroup$ – adnauseam Nov 29 '18 at 14:29