5. Сортировка методом Шелла

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

Сортировка с убывающими расстояниями:

Расстоянием h между двумя элементами a[j] и a[i] называется положительная разность их индексов. Например, расстояние между элементами a[2] и a[6] равно 4 (h = 62).

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

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

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

Все t приращений обозначим через h₁, h₂, ..., h_t с условиями

h_t = 1, h_i+1 < h_i, i=1, …, t1.

Каждая h-сортировка программируется как сортировка простыми включениями.

Программа сортировки методом Шелла может иметь следующий вид:

Procedure ShellSort;

Var i, j, k, t, m: integer;

x: TElement;

h: Array [1..20] Of integer;

Begin

t:= Round(Ln(N)/Ln(3))-1;

If t = 0 Then t:= 1;

h[t]:= 1;

For m:= t-1 Downto 1 Do

h[m]:= 3*h[m+1] + 1;

For m:= 1 To t Do Begin

k:= h[m];

For i:= k+1 To N Do Begin

j:= i - k;

While a[j+k-1].Key < a[j-1].Key Do Begin

x:= a[j+k-1];

a[j+k-1]:= a[j-1];

a[j-1]:= x;

j:= j - k;

If j < 1 Then Break;

End {While}

End; {For i}

End; {For m}

End;

В литературе рекомендуется такая последовательность приращений (записанная в обратном порядке):

1, 4, 13, 40, 121,...,

где h_i-1 = 3h_i+1, h_t = 1 и t = log₃(N1). Именно такие параметры задаются в подпрограмме ShellSort. Приемлемой считается также последовательность

1, 3, 7, 15, 31,...,

где h_i-1 = 2h_i+1, и t = log₂(N1). Анализ показывает, что в последнем случае затраты, которые требуются для сортировки N элементов с помощью алгоритма сортировки Шелла, пропорциональны N ^1,2.

6. Сортировка с помощью бинарного дерева

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди N элементов, затем среди N1 элементов и т. д. Понятно, что поиск наименьшего ключа из N элементов требует N1 сравнений, а поиск его среди N1 элементов  еще N2 сравнений.

Улучшить сортировку выбором можно в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью N/2 сравнений можно определить наименьший ключ из каждой пары. При помощи следующих N/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего N1 сравнений мы можем построить дерево выбора, как показано на рисунке 11.1, и определить корень, как наименьший ключ.

Рисунок 11.1  Построение дерева при последовательном выборе из двух ключей

На втором шаге выполняется спуск по пути, отмеченном наименьшим ключом, с последовательной заменой его на «дыру» (или ключ-бесконечность). По достижении (при спуске) элемента-листа, соответствующего наименьшему ключу, этот элемент исключается из дерева и помещается в начало некоторого списка. Результат выполнения этого процесса показан на рисунке 11.2.

Рисунок 11.2  Спуск по дереву с образованием дыр и формирование упорядоченного списка из исключаемых элементов

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

Рисунок 11.3  Заполнение «дыр»

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

При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов; в конечном счете, для хранения возросшего объема информации нужно строить некую древовидную структуру. Также желательно избавиться от необходимости в «дырах», которые в конце заполняют дерево и приводят к большому числу ненужных сравнений. Кроме того, нужно найти способ представить дерево из N элементов в N единицах памяти вместо 2N-1 единиц. Это можно осуществить с помощью метода, который его изобретатель Дж. Уильямс назвал пирамидальной сортировкой.