Алгоритмы сортировки(2 часть)

Сортировка Шелла

Сортировка Шелла является улучшенным методом, основанном на методе прямого включения с уменьшающимися расстояниями.

Как он работает на примере массива:

Расстояние в группах можно уменьшать по разному. Главное, чтобы последнее было еденичным, ведь в самом плохом случае, последний проход сделает всю работу. Рекомендуется начальный шаг взять h(начальное) = n/3, где n - количество элементов массива. И уменьшать его на каждом проходе вдвое h (i-1) = h(i)/2, h(конечное) = 1.

Анализ сортировки Шелла

Известно, что выбор расстояния должен быть таким, чтобы взаимодействие различных цепочек проходило как можно чаще, в частности неизвестно, какие расстояния дают наилучшие результаты. Математический анализ показывает, что для сортировки n элементов методом Шелла затраты пропорциональны n^1,2.

Сравнение различных алгоритмов сортировки

С - количество сравнений, М - количество перестановок.

Время работы различных методов (при n = 256 и 2048)

Улучшенние двоичного включения по сравнению в прямым включением в действительности почти ничего не даёт, а в случае упорядоченного массива даёт отрицательный эффект. Пузырьковая сортировка является наихудшей из всех сравниваемых сортировок. Усовершенствованная версия шейкерной сортировки продолжает оставаться плохой по сравнению с прямым включением и прямым выбором.

Сортировка слиянием (сортировка последовательности)

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

Простое слияние

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

Последовательность а разбивается на две половины б и с. Разбиение происходит следующим образом: первый элемент последовательности а записывается в последовательность б. Второй элемент последовательности а записывается в последовательность с. Третий снова в б, четвертый в с и тд.
Обе последовательности б и с сливаются в а. При этом одиночные элементы последовательности б и с сравниваются и сливаются в последовательность а в порядке возрастания (убывания) образуя упорядоченные пары.
Полученная последовательность а вновь разбивается на две: б и с. Данный шаг аналогичен шагу 1, однако разбиение происходит не на единичные элементы, а на упорядоченные пары, то есть первая пара последовательности а записывается в последовательность б, вторая последовательность с, третья снова в последовательность б, четвертая в последовательность с и т.д.
Слияние последовательности б и с в последовательность а. При этом поочередно сравниваются элементы соответствующих пар последовательности б и с и сливаются в последовательность а в порядке возрастания или убывания образуя упорядоченые четверки.
Повторяя предыдущие шаги разбиваем и сливаем четверки в восьмёрки и ТД, каждый раз удваивая длину слитых под последовательностей до тех пор, пока не будет упорядочены целиком вся последовательность а.

(Пример можно найти в учебнике Царева п. 4.1 с 58)

Анализ сортировки с помощью прямого слияния:

Поскольку на каждом проходе длина под последовательностей увеличивается вдвое и сортировка заканчивается, когда длина подпоследовательности станет больше или равное длине исходной последовательности, то всего будет необходимо log(n) проходов. По определению на каждом проходе все n элементов копируются по одному разу, поэтому общее число перестановок равно M=nlog(n). Количество сравнений всегда будет меньше количества перестановок.

Естественное слияние

При сортировки простым слиянием данные разбиваются и сливаются подпоследовательности длина которых равна степени двойки, однако данные исходной последовательности могут быть уже частично упорядочены. В этом случае целесообразно просто объединить уже упорядоченные подпоследовательности. Упорядоченные подпоследовательности называют сериями. Таким образом, сортировки естественным слиянием объединяются в серии, а не в подпоследовательности фиксированной длины. Если сливаются две последовательности, каждая из n серий, то результирующая также содержит ровно n серий. Следовательно, при каждом проходе общее число серий уменьшается вдвое и общее число пересылок в самом плохом случае будет равно nlog(n), а в других случаях меньше.

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

Иными словами, число пар кроликов создает ряд, каждый член кото рого равен сумме двух предыдущих. Этот ряд известен как ряд Фибоначчи, а сами числа - как числа Фибоначчи.

При многофазной сортировке слиянием распределений серий происходит с тремя последовательностями. Две из которых являются входными, одна выходной. На каждом проходе элементы из двух входных последовательностей сливаются в третью. Как только одна их входных последовательностей исчерпывается она становится выходной.

Слияние начинается с двух последовательностей f1 и f2,, организованных в виде серий длины 1, а серии их f1 и f2 обьединяются, образуя серии длины 2 и записываются в третью последовательность f3. Слияние происходит до послного опустошения последовательности f2, затем обьединяем оставшиеся серии длины 1 из f1 с таким же количеством серий длины 2 из f3. В результате получаются серии длины 3, которые помещаются в файл f2. Затем обьединяется серии длины 2 из f3 с сериями длины 3 из f2.

Затраты на любую последовательную сортировку пропорциональны числу требуемых проходов, так как по определению при каждом из проходов копируются все данные. Один из способов сократить это число -распределять серии в более чем две последовательности. Слияние г серий поровну распределенных в N последовательностей даст в результате г/N серий. Второй проход уменьшит это число до г/N2, третий - до г/N3 и т. д., после k проходов останется г/N* серий. Поэтому общее число проходов, необходимых для сортировки n элементов с помощью N-путевого слияния, равно k = $log_Nn$

Поскольку в каждом проходе выполняется n операций копирования, то в самом плохом случае понадобится M = $n *log_Nn$ таких операций.