D1: [Цикл по s.] Выполнить шаг D2 при s =t –1, t-2, …, 0, после чего завершить процедуру.

D2: [Цикл по j.] Присвоить h¬h_s и выполнить шаг от D3 до D6 при h < i < N. (Для сортировки элементов, отстоящих один от другого на h позиций, воспользуемся методом простых вставок и в результате получим K_i K_{i + h} для 1iN-h. Шаги от D3 до D6, по существу, такие же, как соответственно от S2 до S5 в алгоритме S.)

D3. [Установка I, K, R.] Присвоить i¬j – h, K¬K_i , R¬R_j .

D4. [Сравнение K: K_i .] Если KK_i , то перейти к шагу D6.

D5. [Перемещение R_i , уменьшение i.] Присвоить R_{i + h} ¬R_i , затем i¬i – h. Если I>0, то возвратиться к шагу D4.

D6. [Перемещение R на место R_{i + h} .] Присвоить R_{i + h} ¬R_i .

Анализ Метода Шелла.

Для рационального выбора последовательности значений смещений сортировки h_{t -1} ,…, h₀ для алгоритма D нужно проанализировать время выполнения как функцию от этих смещений. Такой анализ приводит к постановки очень красивых, но еще не до конца решенных математических задач; никому до сих пор не удалось найти наилучшею возможную последовательность смещений для больших N. Тем не менее известно довольно много интересных свойств сортировки методом Шелла с убывающим смещением.

Метод Флойда

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

Пирамидальная сортировка требует N∙Log₂ N шагов даже в худшем случае. Такие отличные характеристики для худшего случая – одно из самых выгодных качеств пирамидальной сортировки.

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

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

K [ L ],…, K [ R ], такая, что

K[i] ≤ K[2i] & K[i] ≤ K [2i + 1], (1)

длявсякого i = L,…, R/2. Если имеется массив К[1], К[2],…, К[R], который индексируется от 1, то этот массив можно представить в виде двоичного дерева. Пример такого представления при R=10 показан на рисунке 2.

Рис. 2 –Массив ключей, представленный в виде двоичного дерева

Дерево, изображенное на рисунке 2, представляет собой пирамиду, поскольку для каждого i = 1, 2,…, R/2 выполняется условие (1). Очевидно, последовательность элементов с индексами i = R/2+1, R/2+2,…., R (листьев двоичного дерева), является пирамидой, поскольку для этих индексов в пирамиде нет сыновей.

Способ построения пирамиды «на том же месте» был предложен Р. Флойдом. В нем используется процедура просеивания (sift), которую рассмотрим на следующем примере.

Предположим, что дана пирамида с элементами К[3], К[4],…, К[10] нужно добавить новый элемент К[2] для того, чтобы сформировать расширенную пирамиду К[2], К[3], К[4],…, К[10]. Возьмем, например, исходную пирамиду К[3],…, К[10], покачанную на рисунке 3, и расширим эту пирамиду «влево», добавив элемент К[2] =44.

Рис. 3 – Пирамида, в которую добавляется ключ К[2]=44

Добавляемый ключ К[2] просеивается в пирамиду: его значение сравнивается с ключами узлов-сыновей, т.е. со значениями 15 и 28. Если бы оба ключа-сына были больше, чем просеиваемый ключ, то последний остался бы на месте, и просеивание было бы завершено. В нашем случае оба ключа-сына меньше, чем 44, следовательно, вставляемый ключ меняется местами с наименьшим ключом в этой паре, т.е. с ключом 15. Ключ 44 записываетсяв элемент К[4], а ключ 15 – в элемент К[2]. Просеивание продолжается, поскольку ключи-сыновья нового элемента К[4] оказываются меньше его – происходит обмен ключей 44 и 18. В результате получаем новую пирамиду, показанную на рисунке 4.

В нашем примере получалось так, что оба ключа-сына просеиваемого элемента оказывались меньше его. Это не обязательно: для инициализации обмена достаточно того, чтобы оказался меньше хотя бы один сыновей ключ, с которым и производится обмен.

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

Рис. 4 – Просеивание ключа 44 в пирамиду

Алгоритм просеивания в пирамиду допускает рекурсивную формулировку:

1)просеивание элемента с индексом temp,

2)при выполнении условий остановки – выход,

3)определение индекса q элемента, с которым выполняется обмен,