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!

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

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) 

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.