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

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

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

1. для цикла: инициализировать массив C с 0 и размером k (диапазон целых чисел)
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 </p>

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

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

A [1a, 2, 1b]

первый цикл

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

секунда для цикла

j = 1: A [1] = 1a

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

третий для цикла

C [2] = 3

четвертый для цикла

* +1045 * = 1 б [2] = 1а с [1] = 1 * * тысячей сорок-шести * * Тысяча сорок-семь J = 2 б [3] = 2 с [2] = 2 * +1048 * * * Тысяча сорок-девять J = 3 б [1] = 1b с [1] = 0

В РЕЗУЛЬТАТЕ:

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

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

Answer 3

Да, 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

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

Answer 4

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

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