Counting Sort - Why go in reverse order during the insertion?

Question

I was looking at the code for Counting Sort on GeeksForGeeks and during the final stage of the algorithm where the elements from the original array are inserted into their final locations in the sorted array (the second-to-last for loop), the input array is traversed in reverse order.

I can't seem to understand why you can't just go from the beginning of the input array to the end, like so :

for i in range(len(arr)): 
        output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] 
        count_arr[arr[i] - min_element] -= 1

Is there some subtle reason for going in reverse order that I'm missing? Apologies if this is a very obvious question. I saw Counting Sort implemented in the same style here as well.

Any comments would be helpful, thank you!

Cinemascope

Answer 1

Stability. With your way, the order of equal-valued elements gets reversed instead of preserved. Going over the input backwards cancels out the backwards copying (that -= 1 thing).

Dichloride

Answer 2

To process an array in forward order, the count / index array either needs to be one element larger so that the starting index is 0 or two local variables can be used. Example for integer array:

def countSort(arr): 
    output = [0 for i in range(len(arr))] 
    count = [0 for i in range(257)]         # change
    for i in arr: 
        count[i+1] += 1                     # change
    for i in range(256):
        count[i+1] += count[i]              # change
    for i in range(len(arr)): 
        output[count[arr[i]]] = arr[i]      # change
        count[arr[i]] += 1                  # change
    return output

arr = [4,3,0,1,3,7,0,2,6,3,5]
ans = countSort(arr) 
print(ans) 

or using two variables, s to hold the running sum, c to hold the current count:

def countSort(arr): 
    output = [0 for i in range(len(arr))] 
    count = [0 for i in range(256)]
    for i in arr: 
        count[i] += 1
    s = 0
    for i in range(256):
        c = count[i]
        count[i] = s
        s = s + c
    for i in range(len(arr)): 
        output[count[arr[i]]] = arr[i]
        count[arr[i]] += 1
    return output

arr = [4,3,0,1,3,7,0,2,6,3,5]
ans = countSort(arr) 
print(ans) 

Carolecarolee

Modified your first one to not use an extra element: repl.it/repls/EasyBulkyGlueware#main.py – Dichloride

@superbrain - yes, I missed the link. I don't understand count[i-255], if i == 0, then it is indexing count[-255]? Does python have some type of "wraparound" indexing? – Carolecarolee

Partially, yes. It doesn't wrap around in both directions forever, just backwards and only once. So count[-1] is the last element and count[-len(count)] is the first element. If it did wrap around to the right, then I'd use +1 instead of -255. But that's just details. My real point is that the count of the largest value isn't needed, so we can throw it away or rather overwrite it instead of having an extra element like you're talking about. – Dichloride

In other words, you could also do this: repl.it/repls/FunnyTrainedStrings#main.py – Dichloride

@superbrain - the issue with either way is that a conditional gets involved (check for negative index or check for < 255), which in the case of a complied language, such as C / C++, creates a time penalty. My second example would be slightly faster with a compiled language. – Carolecarolee

Well the check for negative index is there whether you use a negative index or not. But yes, negative indexes are still slower. I'm just disagreeing with "needs to be one element larger". – Dichloride

@superbrain - I updated my answer since it wasn't clear, "either needs to be one larger or use local variables". If local variables are used, it doesn't need to be one larger, as shown in the second example. It could also avoid storing a count for the maximum value, but that involves a conditional (if) statement, which is normally a bit slower. – Carolecarolee

Answer 3

Here We are Considering Stable Sort --> which is actually considering the Elements position by position.

For eg if we have array like

arr--> 5 ,8 ,3, 1, 1, 2, 6

     0 1 2 3 4 5 6 7 8 

count-> 0 2 1 1 0 1 1 0 1

Now we take cummulative sum of all frequencies

     0 1 2 3 4 5 6 7 8 

count-> 0 2 3 4 4 5 6 6 7

After Traversing the Original array , we prefer from last Since we want to add Elements on their proper position so when we subtract the index , the Element will be added to lateral position.

But if we start traversing from beginning , then there will be no meaning for taking the cummulative sum since we are not adding according to the Elements placed. We are adding hap -hazardly which can be done even if we not take their cummulative sum.

Putrid