Изменение алгоритма сортировки подсчета

Question

Это алгоритм сортировки подсчета. Я хочу изменить последний цикл for на for j<---1 to n. Я знаю, что это будет правильно, но я хочу показать это для одного из моих друзей. Как я могу написать свою причину? Пожалуйста, помогите мне! Благодарю.

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

Приведенный выше код абсолютно правильный. Если вы измените последний цикл с 1 to n, результат будет правильным, но относительный порядок элементов с одинаковыми значениями будет отменен. Например, если исходный массив содержит только 3 элемента, и все из них можно назвать 5, то в случае 1 to n последние пять будут первым элементом, вторым последним 5 будет второй элемент, а первые 5 будут последним элементом т.е. относительный порядок одних и тех же элементов был отменен.

Answer 2

Нет, последний цикл должен быть n downto 1, так как это приводит к своего рода, являющейся stable sort (то есть, если два элемента равны, то они останутся в их первоначальном порядке).

Если вы измените его на 1 to n, то все равные подпоследовательности списка будут помещены в обратном порядке. Иногда это не имеет значения, но иногда это происходит, и, поскольку нет никакого недостатка в использовании n downto 1, это должно быть предпочтительным.