Сортировка с использованием радикальной сортировки

Question

Я читал radix sort с этого сайта я запутался в 3-м for loop:

for (i = n - 1; i >= 0; i--) {
    output[freq[(arr[i] / place) % range] - 1] = arr[i];
    freq[(arr[i] / place) % range]--;
}

Почему они запускали его с конца, а когда я пытался запустить его с 0, он дает мне неправильный ответ? Любое объяснение или решение будет оценено.

Answer 1

Так как freq содержит совокупное количество элементов в каждой позиции в диапазоне. То есть для диапазона i=0-9, freq[i] содержит количество цифр, которые размещены на позициях 0, ..., i,

Алгоритм использует freq чтобы отслеживать, сколько элементов нужно нарисовать из исходного массива в выходной массив для каждой позиции.

Предполагая 10,21,17,34,44,11,654,123 в качестве входных данных, запустив счетную сортировку для первой незначащей цифры:

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9: 

freq будет как:

0: 1
1: 3
2: 3
3: 4
4: 7
5: 7
6: 7
7: 8
8: 8
9: 8

Итак, массив становится 10,21,11,123,34,44,654,17.

Вам нужно вернуться назад, чтобы сохранить исходный порядок чисел с той же цифрой, потому что, как freq построено. Предположим, вы хотите разместить 34 в нужном месте на выходе. Согласно freq массив, если цикл вперед, вы бы поместили его на 7-ю позицию, что неверно. Если вы вернетесь назад, вы уже поставили 654 и 44 до 34, поэтому freq[4]=5 к тому времени это правильное место.