changing counting sort algorithm

Question

Hi!

This is a counting sort algorithm. I want to change the last for loop of it to for j<---1 to n. I know that this will be correct, but I want to show this for one of my friends. How can I write my reason for it? Please help me! Thanks.

Counting Sort(A[1,..n]) //C[1,...k] is the temporary memory and k is the range of integers
   for  i<-- 1 to k
      C[i]<-- 0
   for  j<-- 1 to n
      C[A[j]]<--C[A[j]]+1
   for  i<--2 to k
      C[i]<--C[i]+C[i-1]
   for  j<--n downto 1
      B[C[A[j]]]<--A[j]
      C[A[j]]<--C[A[j]]-1

Answer 1

No, the last loop should be n downto 1 as this results in the sort being a stable sort (i.e. if two elements are equal, they will remain in their original order).

If you change it to 1 to n, then all the equal subsequences of the list will be placed into the reverse order. Sometimes it doesn't matter, but sometimes it does, and since there's no disadvantage in using n downto 1, it should be preferred.

Answer 2

The above code is absolutely correct. If you change the last loop from 1 to n the output will be correct but the relative order of the elements with same values will get reversed. For e.g - If original array contains only 3 elements and all of them are let say 5 then in case of 1 to n, the last five will be the first element, second last 5 will be the second element and the first 5 will be the last element i.e relative order of same elements got reversed.