Сортировка массива сложным выбором (с помощью двоичного дерева)

Метод сортировки основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов n-2 сравнений. Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец при помощи всего n-1 сравнений мы можем построить дерево, как показано на рис.1, выбора и определит корень, как наименьший ключ. На втором шаге мы спускаемся по пути, указанном наименьшим ключом, и исключаем его, последовательно заменяя либо на "дыру" (или ключ бесконечность), либо на элемент, находящийся на противоположной ветви промежуточного узла Элемент оказывается в корне дерева, вновь имеет наименьший ключ среди оставшихся и может быть исключен. После n таких шагов дерево становится пустым (т.е. состоит из "дыр"), и процесс сортировки закончен.

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

Рисунок 7. Сортировка бинарным деревом

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

Пирамида определяется как последовательность ключей

hl, hl+1,..., hr, такая, что hi <= h2i, hi <= h2i+1

для всякого i =l,...,r/2. Если двоичное дерево представлено в виде массива, как показано на рис.1, то, следовательно, деревья сортировки на рис.2 и 3 являются пирамидами, и, в частности, элемент h1 пирамиды является ее наименьшим элементом h1 = min (h1... hn).

Теперь предположим, что дана пирамида с элементами hl+1,..., hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl,..., hr. Возьмем, например, исходную пирамиду h1,...,h7, показанную на рис.2, и расширим эту пирамиду "влево", добавив элемент h1=44. Новый элемент x сначала помещается в вершину дерева, а затем "просеивается" по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом формируется новая пирамида. На рисунке 8 продемонстрирована пирамидальная сортировка.

Рисунок 8. Процесс построения дерева

В данном примере значение 44 сначала меняется местами с 06, затем 12, и так формируется дерево. Далее процесс просеивания будем формулировать следующим образом: i, j - пара индексов, обозначающих элементы, которые нужно менять местами на каждом шаге просеивания.

Для восьми элементов из нашего примера минимальное и максимальное количества пересылок дают следующие исходные последовательности:

Мmin = 13 для последовательности

94, 67, 44, 55, 12, 42, 18, 6

Mmax=24 для последовательности

18, 42, 12, 44, 6, 55, 67, 94

Среднее число пересылок равно приблизительно nlog (n) /2 и отклонения от этого значения сравнительно малы.

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

На рисунке 9 продемонстрирована сортировка методом Шелла:

Рисунок 9. Сортировка Шелла

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

На каждом шаге в сортировке участвует либо сравнительно мало элементов, либо они уже довольно хорошо упорядочены и требуют относительно мало перестановок. Очевидно, что этот метод дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки. Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через

h1, h2,..., hn с условиями ht=1, hi+1 < hi.

Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется барьер. Ясно, что каждая h-сортировка требует собственного барьера и что программа должна определять его место как можно проще.