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

Сортировка называется сравнение и подсчет.

40 4 5 20 7 14 15 -2 k

0 0 0 0 0 0 0 0 count

0 1 1 1 1 1 1 1

0 0 0 0 0 0 1

0 0 0 0 1

0 8 7 1 5 6 4 3 2

20

Count[i] – количество элементов ki.

Расстановка элементов в соответствии Result[Count [i] + 1]:=k[i]

Распределяющий подсчет

В этом алгоритме ключами могут быть целые числа или приводимые к целым в диапазоне от a до c.

Ki Э [a…c]

a ≤ Ki ≤ C

a = min{Ki} – O(n)

c = max{Ki} – O(n)

Для подсчета количества используется вспомогательный массив

a = min{k}= 2

c = max{k} = 5

count [a…c]

4 2 4 5 4 2

0 0 0 0 count

2 3 4 5

2 0 3 1 count[k[i]++]

2 3 4 5

I этап инициализация массива count 0 0 0 0

II этап подсчет одинаковых ключей Count[i]++

2. 0 3 1

III этап – заметим, что значением самой правой ячейки count показывает, сколько ячеек необходимо зарезервивать в результирующем массиве под хранение значения K[i] . В данном случае одна ячейка отводится под хранение 5, три ячейки под значения 4, 0 ячеек – под тройку и две ячейки под значение двойки. При помощи цикла расположим элементы по зарезерванным позициям. Заметим, что тройки могли бы начать располагаться после всех двоек, т.е. после количества, указанной в count.. Четверки располагаются по двойки и тройки, т.е. с позиции count[2]+count[3], а прибавляя count [4] мы получаем самую правую позицию, которую может занять k[i] ключ.

IV этап – расположение элементов.

|c - a| - должно быть небольшое

2*O(N) + O(c-a) + O(N) + O(c-a-1) + O(N)= const O(N) + const O(c-a)

Класс сортировок слиянием

Объединение двух упорядоченных последовательностей, которые обнаруживаются в исходной последовательности. В зависимости от принципа обнаружения упорядоченных фрагментов (подпоследовательностей) различают естественную и фиксированную сортировку двухпутевым слиянием.

Естественное двухпутевое слияние – едс

В обоих алгоритмах ЭДС и ФДС используется память объемом 2N. Попеременно одна область служит источником, а другая – получателем предупорядоченных последовательностей. В источнике одна предупорядоченная расположена слева направо, а другая справа налево (в конце). В каждый момент времени сравнивается очередные элементы подпоследовательностей (если они еще не пустые), и в результат записывается наименьший (наибольший из этой пары).

Естественная упорядоченность нарушается, если следующий за слитным элементом нарушил упорядоченность. В получателе меняется направление записи, а в источнике начинается новая пара упорядоченных подпоследовательностей. Это завершается если в источнике один и тот же элемент рассматривается с обеих сторон. После чего источник с получателем меняются ролями

_ ______ _____________

3 4 2 5 3 10 15 10 8 11 5 2

2 3 4 5 11 3 10 15 10 8 5 2

2 2 3 4 5 5 8 10 11 15 10 3

2 2 3 3 4 5 5 8 10 10 11 15

Наибольшее число операций выполняется при проверке ступеньки вниз, т.е. при выискивании упорядоченности. Чтобы отказаться от этих вычислений, фиксируем количество элементов слияемой последовательности: замечая, что последовательность из одного элемента упорядочена, объединяя такие последовательность, мы гарантированно получаем последовательность из двух элементов, а в следующий раз сливая из двух, получаем 4 элемента и т.д., кроме, быть может, последней подпоследовательности, если число элементов не является степенью 2.