Метод предсортировки и слияния

В основе данного метода лежит следующий алгоритм: основной массив разбивается на два дочерних, в отношении каждого из которых осуществляется первичная сортировка. Затем отсортированные массивы сливаются, и полученный массив подвергается вторичной сортировке - в результате получаем отсортированный массив. Блок-схема данного метода приведена на рис. 3.12.

 

Метод максимумов

1) Просматривая массив от первого элемента, найти максимальный элемент и поместить его в последнюю ячейку промежуточного массива, а в основном массиве ячейка, содержащая найденный максимум, обнуляется.

2) Просматривая массив от первого элемента, найти максимальный элемент и поместить его в предпоследнюю ячейку промежуточного массива, а в основном массиве ячейка, содержащая найденный максимум, обнуляется.

3) И так далее.

Блок – схема метода приведена на рис. 3.12.

 

3.1.7. Шейкер [1] -сортировка

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

Работа этого метода показана на рис. 3.4.

Рис. 3.4. Пример шейкер-сортировки

 

Достоинства: уменьшение избыточных повторных проверок.

Недостаток: не изменилось число обменов элементов.

3.1.8. Сортировка включениями с убывающим приращением
(сортировка Шелла)

Некоторое усовершенствование сортировки простыми включениями было предложено Д.Л. Шеллом в 1959 году.

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

Рассмотрим пример, представленный на рис. 3.5. На первом проходе отдельно группируются и сортируются все элементы, отстоящие друг от друга на четыре позиции. Этот процесс называется 4-сортировкой. В примере из восьми элементов каждая группа содержит ровно два элемента. После этого элементы вновь объединяются в группы с элементами, отстоящими друг от друга на две позиции, и сортируются заново. Этот процесс называется 2-сортировкой. Наконец, на третьем проходе все элементы сортируются обычной сортировкой, или 1-сортировкой.

Рис. 3.5. Пример сортировки включениями с убывающим приращением

 

Приращения не должны быть кратны друг другу. Это позволяет избежать явления, где каждый проход сортировки объединяет две цепочки, которые ранее никак не взаимодействовали (см. рис. 3.5).

 

Сортировка с помощью дерева

Сортировка сводится к разбиению массива на пары и выбору меньшего среди них, последующему разбиению и выбору. Таким образом строим дерево выбора:

44 55 12 42 94 18 06 67

\ / \ / \ / \ /

44 12 18 06

\ / \ /

12 06

\ /

 

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

44 55 12 42 94 18 __ 67

\ / \ / \ / \ /

44 12 18 __

\ / \ /

12 __

\ /

__

 

44 55 12 42 94 18 67

\ / \ / \ / /

44 12 18 67

\ / \ /

12 18

\ /

 

Повторив последний шаг несколько раз,дерево пропадает.

 

Пирамидальная сортировка

Пирамида – двоичное дерево с упорядоченными листьями (корень дерева – наименьший элемент). Пирамиду можно представить в виде массива (смотри рис.3.6.). Первый элемент пирамиды является наименьшим.

 

Рис. 3.6. Массив, расположенный в виде бинарного дерева

 

Просеивание – построение новой пирамиды: помещение нового элемента в вершину дерева, далее он перемещается («просеивается») по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх.

Например, возьмём исходную пирамиду, показанную на рис. 3.7,а, и расширим эту пирамиду «влево», добавив элемент h₁=44. Значение 44 сначала меняется местами с 06, затем с 12, и так формируется дерево, показанное на рис. 3.7,б.

Рис. 3.7 а) пирамида из семи элементов; б) просеивание элемента 44 через пирамиду.

 

Способ построения пирамиды, предложенный Р.У. Флойдом: пусть дан массив h₁,…h_n, тогда элементы h_n/2+1…h_n уже образуют пирамиду. Эти элементы составляют последовательность, которую можно рассматривать как нижний ряд соответствующего двоичного дерева (смотри рис. 3.8). Пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место.

 

 

Рис. 3.8. Построение пирамиды

 

67 X₁..X_n

 

06 h₁

/ \ / \

42 12 h₂ h₃

/ \ / \ / \ / \

55 94 18 44 h₄ h₅ h₆ h₇

 

h₁ (наименьшее число) записывается в отсортированный массив, X записывается в h₁ и просеивается. Это повторяется, пока не закончатся свободные элементы. После этого h1 записывается в отсортированный массив, а на его место записывается меньший элемент из следующего уровня, на место которого в свою очередь записывается меньший элемент следующего уровня этой ветви, и т.д. На место элемента из нижнего уровня записывается последний по счету элемент.

Пример пирамидальной сортировки представлен на рис. 3.9.

Рис. 3.9. Пример пирамидальной сортировки

 

3.1.11. Быстрая сортировка (метод Хоора)

Этот метод разработан К. Хоором в 1962 году.

Суть метода заключается в том, чтобы выбрать случайным образом какой-то элемент, просмотреть массив, двигаясь слева направо, пока не будет найден элемент, больший выбранного. Затем просмотреть его справа налево, пока не будет найден элемент, меньший выбранного. После этого поменять эти элементы местами и продолжить «просмотр с обменом», пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую – с меньшими элементами, чем выбранный, и правую – с большими элементами. Разделив массив, нужно сделать то же самое с обеими полученными частями, затем с частями этих частей и т.д., пока каждая часть не будет содержать только один элемент.

Пример первого разделения массива проиллюстрирован на рис. 3.10.

Рис. 3.10. Разделение

 

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

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