изменение алгоритма сортировки

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, так как в результате сортировка будет стабильной сортировкой (т. Е. Если два элемента равны, они останутся в своем первоначальном порядке).

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