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

Question

Я прочитал алгоритм сортировки подсчета, который, как это:

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 

Я хочу знать, что если я изменю последнее для этого: for j<--1 to n, алгоритм будет правильным тоже ?? ? (есть ли способ показать, что с этим «для» алгоритм будет правильным?)

также таким же образом также и алгоритм?

спасибо

Answer 1

Алгоритм является правильным в обоих направлениях. Он также стабилен, как и сейчас.

Если вы изменили последнее for на то, что вы сказали, оно перестанет быть стабильным.

В принципе, C[i] = how many elements <= i exist после окончания третьего for петля. Так C[A[j]] дает вам последнюю позиции элемента со значением A[j] в отсортированном порядке, C[A[j]] - 1второго последний положения элемента со значением A[j] и так далее. Вот почему вы уменьшаете значения в C.

Из-за этого вы должны начать повторять исходный массив в обратном порядке, если вам нужна стабильность: так что последний элемент со значением x в вашем исходном массиве ставится первым в новом массиве.Итерирование исходного массива в обратном порядке гарантирует, что x ставится после все остальные значения, равные x, что делает алгоритм стабильным.

Answer 2

Алгоритм кажется стабильным, как и для меня.

Если вы измените последний for, тогда он по-прежнему будет правильным, но не будет стабильным. (изменит порядок равных элементов).

Answer 3

Хорошо, короткие объяснения алгоритма:

1. цикла: инициализировать массив C с 0, и размером к (диапазон целых чисел)
2. цикла: подсчитать число и сохранить номер в C
3. для цикла: суммируйте общее количество значений, не равных данному Пример: существует пять 1, три 2, два 3 => c [1] = 5, c [2] = 8, c [3] = 10
4. для цикла: начиная с конца массива A и помещая его в соответствующее значение C в значении B и уменьшении значения в C

Поскольку вы сохраняете последнее положение для разных чисел в массиве C, вы также должны начинать конец массива A. Если вы просто работаете с целыми числами, алгоритм также будет правильным, если вы начнете с j < - 1 до n

Стабильность не задана: например,то 1s бы в обратном порядке

Пример: (я добавил индексы к один раз, два показывают порядок)

А [1a, 2, 1b]

первый цикл

• С [1] = 0
• C [2] = 0

второй цикл

J = 1: [1] = 1а

C[1] = 1 
C[2] = 0 

J = 2: A [2] = 2

C[1] = 1 
C[2] = 1 

J = 3: A [3] = 1b

C[1] = 2 
C[2] = 1 

третий цикл

С [2] = 3

четвёртого цикла

= 1 б [2] = 1a с [1] = 1

J = 2 б [3] = 2 с [2] = 2

J = 3 б [1] = 1b с [1] = 0

в результате чего:

• б [1] = 1b
• б [2] = 1a
• б [3] = 2

=> не стабильна

Answer 4

Да, 1 to n все равно будет сортироваться правильно, но вы будете использовать стабильность, которую имеет n downto 1.

После второго цикла C содержит суммарную сумму, эти значения являются в точности знаками последнего элементов каждого номера в конечном массиве. Вот почему возвращение назад дает стабильность.

Вы можете получить стабильность 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 
    last <-- C[1] 
    C[1] <-- 0 
    for i<--2 to k 
     tmp <-- C[i] 
     C[i]<--C[i-1]+last 
     last <-- tmp 
    for j<--n downto 1 
     B[C[A[j]]]<--A[j] 
     C[A[j]]<--C[A[j]]-1 

накопленная сумма становится немного некрасиво. Но я уверен, что это можно было бы сделать лучше.