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

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

Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через

hi, Л2, .... ht

с условиями

Л/=1, hi+i<hi. (2.12)

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

Ясно, что каждая ft-сортировка требует собственного барьера и что программа должна определять его место как можно проще. Поэтому массив а нужно дополнить не одной компонентой а [0], а Н\ компонентами, так что теперь он описывается как

а: аггау[- Л,. .п] of item

Этот алгоритм представлен в виде процедуры, названноИ Shellsort [2.П] ( сортировка Шелла ) в программе 2.

для t=A.

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

procedure shellsort; const t = 4;

var i,j,k,s: index; x: item; m: 1. .t; h: array [1 .. /] of integer; begin Ml] := 9; кЦ] 5; h[3] :== 3; h[4] := 1; for w := 1 to / do

begin к := h[m]; s := -k; [место барьера}

for / := k+l to n do begin X := a[i\; j :- i-k;

if s=0 then s := -k; s := s+1; a[s] := л:; while X .key < a[j] .key do begin a[j+k] := a[j]; j := j-k end ;

alj+k] := X

Программа 2.6. Сортировка Шелла.

происходило как можно чаще. Можно сформулировать следующую теорему:

Если -рассортированная последовательность г-сортируется,. то она остается -рассортированной.

Кнут [2.8] указывает, что разумным выбором может быть такая последовательность приращений (записанная в обратном порядке):

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

где hk~i = З/г* -f 1, Л, = 1 at - [logan] - 1. Он рекомендует также последовательность

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

Где Ла , = 2ftft + l, lit=l и t= [login] -I. Дальнейший анализ показывает, что в последнем случае затраты, которые требуются для сортировки п элементов с помощью алгоритма (Сортировки Шелла, пропорциональны п. Хотя это - значительное улучшение по сравнению с п^, мы не будем в дальнейшем обращаться к этому методу, поскольку известны алгоритмы, работающие еще лучше.

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

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

ключа из п элементов требует п - 1 сравнений, а поиск е реди п-1 элементов требует п - 2 сравнений. Итак, i можно улучшить эту сортировку выбором? Это можно лать только в том случае, если получать от каждого прохо! больше информации, чем просто указание на один, наимец ший элемент.. Например, с помощью п/2 сравнений моя, определить наименьший ключ из каждой пары, при noMoujJ *

44 12

55 12

18 06

94 18 06 67

Рис. 2.3. Циклический выбор из двух ключей.

следующих п/4 сравнений можно выбрать наименьший щ каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего п-1 сравнений мы можем построить дереве выбора, как показано на рис. 2.3, и определить корень кап наименьший ключ [2.2].

Рис. 2.4. Выбор наименьшего ключа.

На втором шаге мы спускаемся по пути, указанному наименьшим ключом, и исключаем его, последовательно заменяя либо на дыру (или ключ оо), либо на элемент, находя* щийся на противоположной ветви промежуточного уз- (см. рис. 2.4 и 2.5). Элемент, оказавшийся в корне дереве вновь имеет наименьщий ключ (среди оставшихся) и моЖ^ быть исключен. После п таких шагов дерево становится тым (т. е. состоит из дыр ), и процесс сортировки закончеЧ Отметим, что каждый из п шагов требует лишь log2n сра^ нений. Поэтому вся сортировка требует лишь поряД* . n-Iog2n элементарных операций, не считая п шагов, которь! необходимы для построения дерева. Это - значительное улУ'