1
$\begingroup$

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 us modified_count—an array that stores the number of items with a key less than i.

  • 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).

$\endgroup$
4
  • $\begingroup$ Can you check what is happening if you run on a smaller example such as [2,2,2,3,3]? $\endgroup$ Commented Nov 29, 2018 at 4:41
  • $\begingroup$ Oops, thanks for catching that; I really appreciate it! :D I wasn't initializing the output array properly. I had output = [0] * max_int when I should've had output = [0] * len(input_list) so I was getting off-by-one errors. I fixed it in my repl and in the original question. $\endgroup$ Commented Nov 29, 2018 at 14:29
  • $\begingroup$ Suppose you have a sorted array and you want to know how many elements are smaller than $x$. You just find the index of $x$ in the array and that's your answer. This is the same principle but in reverse. $\endgroup$ Commented Nov 30, 2018 at 15:07
  • $\begingroup$ Ahhh, thank you for that insight! I was overthinking this. That's so obvious in hindsight. Much obliged! What a clever algorithm. I hope somebody may benefit from my silliness. $\endgroup$ Commented Nov 30, 2018 at 21:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.