Для ТОГО чтобы рассортировать элементы, надо выполни^ п шагов просеивания: после каждого шага очередной элемео! берется с вершины пирамиды. Вновь встает вопрос, куд. помещать элементы с вершины и возможна ли сортировц. in situ. Да, такое решение существует! На каждом шаге цз пирамиды выбирается последняя компонента (скажем, и верхний элемент пирамиды помещается на освободившеес, место X, а X просеивается на свое место. В этом случае нщ, ходимо совершить п-1 шагов, что показано на пример

Таблица 2.7. Пример пирамидальной сортировки

пирамиды, приведенной в табл. 2.7. Этот процесс описывается с помощью процедуры sift (программа 2.7) следующим образом:

г := и;

while г > 1 do

begin X :== аЩ; а[1] ;= а[г]; а[г] := х; г:=г-1; sift{l,r)

Из табл. 2.7 видно, что на самом деле в результате мы полу чаем последовательность в обратном порядке. Но это легко можно исправить, изменив направление отношения поряД! в процедуре sift. В результате мы получаем процедуре Heapsort, показанную в программе 2.8.

Анализ пирамидальной сортировки. С первого взгляД' неочевидно, что этот метод сортировки дает хорошие резу- таты. Ведь элементы с большими ключами вначале просе ваются влево, прежде чем, наконец, окажутся справа. ствительно, эта процедура не рекомендуется для такого f большого числа элементов, как, скажем, в нашем пример- Однако для больших п пирамидальная сортировка оказ!

procedure heapsort;

var l,ri index; x: item;

procedure sift; label 13; var ij: index; be,gin t := /; У := 2*i; x := ф!; while / r do

begin if / < r then

if a[j] .key < аУ+Ц .key then / if x .key o[;] fcej then goto 13; o[/]:=o[/];i:-j;j:=2*; end ; 13: a[i] := л: end ;

begin /:- (и div 2) + 1; r := n; while / > 1 do

bin / :- /-1; sift end ; while r -> 1 do

begin л; := я[1]; a[l] := a[r]; a[r] :== дг; r:=r--l;sift

aid [heapsort]

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

вается очень эффективной, и чем больше п, тем она эффективнее- даже по сравнению с сортировкой Шелла.

В худшем случае необходимы п/2 шагов, которые просеивают элементы через log (п/2), log (п/2-1), log(rt-1) позиций (здесь берется целая часть логарифма по основанию 2). Следовательно, на фазе сортировки происходит п- 1 просеиваний с самое большее log(n-1), log(n - 2), I Пересылками. Кроме того, требуются п - 1 пересылок для Того, чтобы отложить просеянный элемент вправо. Отсюда видно, что пирамидальная сортировка требует n-log(n) ша- Ов даже в худшем случае. Такие отличные характеристики Для худшего случая - одно из самых выгодных качеств пира-идальной сортировки.

Не совсем ясно, в каких случаях можно ожидать наимекь-бй (или наибольшей) эффективности. Но в принципе для Пирамидальной сортировки, видимо, больше всего подходят Учаи, когда элементы более или менее рассортированы Обратном порядке, т. е. для нее характерно неестественное

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

Mm!n= 13. для последовательности 94 67 44 55 12 42 18 6

Л^п1ах = 24 для последовательности 18 42 12 44 6 55 67 94

Среднее число пересылок равно приблизительно 4 **bgn и отклонения от этого значения сравнительно малы.

2Л.6. Сортировка с разделением

После того как мы обсудили два усовершенствованных метода сортировки, основанных на принципах включения и выбора, мы введем третий, улучшенный метод, основанный на принципе обмена. Учитывая, что сортировка методом пу- эырька в среднем была наименее эффективной из трех алго 1 ритмов простой сортировки, мы должны требовать значитель-ного улучшения. Однако неожиданно оказывается, что усовершенствование сортировки, основанной на обмене, которое мы здесь будем обсуждать, дает вообще лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель К. Хоор окрестил его быстрой сортировкой (2.5, 2.6].

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что нам даны п элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего п/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться с двух концов к середине. Разумеется, это возможно, только если мы знаем, что элементы расположены строго в обратном порядке. Но все же этот пример наводит на некоторые мысли.

Попробуем рассмотреть следующий алгоритм: выберем* случайным образом какой-то элемент (назовем его х), прО смотрим массив, двигаясь слева направо, пока не найдем элемент с,- > х, а затем просмотрим его справа налево, пока не найдем элемент uj <i х. Теперь поменяем местами эти дв элемента и продолжим процесс просмотра с обменом , пока два просмотра не встретятся где-то в середине массива-В результате массив разделится на две части: левую -с клЮ'