Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n - 1 элементов и так далее. Обнаружение наименьшего среди n элементов требует — это очевидно — n - 1 сравнения, среди n - 1 уже нужно n - 2 сравнений и так далее. Как же в таком случае можно усовершенствовать упомянутый метод сортировки? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n /2 сравнений, можно определить в каждой паре ключей меньший. С помощью n /4 сравнений — меньший из пары уже выбранных меньших и т. д. Проделав n - 1 сравнений, мы можем построить дерево выбора, вроде представленного на рис. 2.2 и идентифицировать его корень как нужный нам наименьший ключ.
Рис. 2.2. Повторяющиеся выборы среди двух ключей
Второй этап сортировки — спуск вдоль пути, отмеченного наименьшим элементом, и исключение его из дерева путем замены на пустой элемент (дырку) (рис. 2.3). Элемент, передвинувшийся в корень дерева (рис.2.4.), вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (т. е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание — на каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобится порядка n * log n элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение не только прямого метода, требующего n 2 шагов, но и даже метода Шелла, где нужно 1.2 n шагов. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Ведь, в конце концов, для сохранения избыточной информации, получаемой при начальном проходе, создается некоторая древообразная структура. Наша следующая задача — найти приемы эффективной организации этой информации.
44 12 18
44 55 12 42 94 18 67
Рис. 2.3. Выбор наименьшего ключа.
Рис.2.4.Заполнение дырок.
Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено все дерево, и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из n элементов, которое требует лишь n единиц памяти, а не 2 n - 1, как это было раньше. Этих целей действительно удалось добиться в методе пирамидальная сортировка, изобретенном Д.Уилльямсом, где было получено, очевидно, существенное улучшение традиционных сортировок с помощью деревьев. Пирамида определяется как последовательность ключей hl, hl+1,...,hr, такая, что
hi <= h2i и hi< =h2i+1, для i = l,..., r/2.
Если любое двоичное дерево рассматривать как массив по схеме на рис. 2.6, то можно говорить, что деревья сортировок на рис. 2.7 и 2.8 суть пирамиды, а элемент h1, в частности, их наименьший элемент: h1 = min(h1,h2,…, hn).
 |
Рис. 2.6. Массив h, представленный в виде двоичного дерева
Рис. 2.7. Пирамида из семи элементов.
Рис. 2.8.Просеивание ключа 44 через пирамиду.
Предположим, есть некоторая пирамида с заданными элементами hl+1,.., hr для некоторых значений l и r и нужно добавить новый элемент x, образуя расширенную пирамиду hl,..., hr. Возьмем, например, в качестве исходной пирамиду h1,...,h7, (показанную на рис. 2.7) и добавим к ней слева элемент h 1 = 44. Новая пирамида получается так: сначала x ставится наверх древовидной структуры, а затем он постепенно опускается вниз, каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12, и в результате образуется дерево, представленное на рис. 2.8. Теперь мы сформулируем тот сдвигающий алгоритм так: i, j — пара индексов, фиксирующих элементы, меняющиеся на каждом шаге местами. Остается лишь убедиться самому, что предложенный метод сдвигов действительно сохраняет неизменными условия, определяющие пирамиду.
Р.Флойдом был предложен некий "лаконичный" способ по строения пирамиды «на том же месте». Его процедура сдвига представлена как программа 2.2. Здесь h 1… h n — некий массив, причем h n/2+1... h n уже образуют пирамиду, поскольку индексов i, j, удовлетворяющих отношениям j = 2 i (или j = 2 i + 1), просто не существует. Эти элементы образуют как бы нижний слой соответствующего двоичного дерева (рис. 2.6), для них никакой упорядоченности не требуется. Теперь пирамида расширяется влево: каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Табл. 2.2 иллюстрирует весь тот процесс, а получающаяся пирамида была показана на рис.2.5
PROCEDURE sift(l,r: index);
LABEL 13;
VAR i, j: index; x:item;
BEGIN i:= l; j:= 2*i; x:= a[i];
WHILE (j<=r) do
BEGIN IF j < r THEN
IF a[j].key > a[j+1].key then j:= j+1;
IF x.key <= a[j].key then goto 13;
a[i]:=a[j]; i:=j; j:=2*j;
END;
13: a[i]:=x
END;
Программа 2.2. Sift
Следовательно, процесс формирования пирамиды из n элементов h 1,..., h n на том же самом месте описывается так:
l:= (n DIV 2) + 1;
WHILE l > 1 DO
BEGIN l:= l-1; sift(l, n) END
Таблица 2.2.Построение пирамиды.
Для того чтобы получить не только частичную, но и полную упорядоченность среди элементов, нужно проделать n сдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший) элемент. И вновь возникает вопрос: где хранить "всплывающие" верхние элементы и можно или нельзя проводить обращение на том же месте? Существует, конечно, такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет x), прятать верхний элемент пирамиды в освободившемся теперь месте, а x сдвигать в нужное место. В табл. 2.3 приведены необходимые в этом случае n - 1 шагов.
Сам процесс описывается с помощью процедуры sift (программа 2.2) таким образом:
r:= n;
WHILE r > 1 DO
BEGIN x:=a[1]; a[1]:=a[r]; a[r]:=x;
r: = r- 1; sift (1,r)
END
Пример из табл. 2.3 показывает, что получающийся порядок фактически является обратным. Однако это можно легко исправить, изменив направление "упорядочивающего отношения" в процедуре sift. В конце концов, получаем процедуру HeapSort (программа 2.3).
Таблица 2.3. Пример процесса сортировки с помощью Heapsort.
procedure HeapSort;
var l,r:index; x:item;
procedure sift;
label 13;
var i,j: index;
begin i:=l; j:=2*i; x:=a[i];
while j<=r do
begin if j<r then
if a[j].key<a[j+1].key then j:=j+1;
if x.key>=a[j].key then goto 13;
a[i]:=a[j];
i:=j;
j:=2*i
end;
13: a[i]:=x
end;
begin l:=(n div 2)+1; r:=n;
while l>1 do
begin l:=l-1; sift
end;
while r>1 do
begin x:=a[1]; a[1]:=a[r]; a[r]:=x;
r:=r-1; sift
end
end;
Программа 2.3. HeapSort
Анализ HeapSort. На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь, в конце концов, большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. И действительно, процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n HeapSort очень эффективна; чем больше n, тем лучше она работает. Она даже становится сравнимой с сортировкой Шелла.
В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log(n /2),log(n /2 -1),…, log(n -1) позиций (целая часть логарифма по основанию 2) Следовательно, фаза сортировки требует n - 1 сдвигов с самое большое log(n - 1), log(n - 2),..., 1 перемещениями. Кроме того, нужно еще n – 1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев HeapSort потребует n * log n шагов. Великолепная производительность в таких плохих случаях — одно из привлекательных свойств HeapSort.
Совсем не ясно, когда следует ожидать наихудшей (или наилучшей) производительности. Но вообще-то кажется, что HeapSort "любит" начальные последовательности, в которых элементы более или менее отсортированы в обратном порядке. Поэтому ее поведение несколько неестественно. Если мы имеем дело с обратным порядком, то фаза порождения пирамиды не требует каких-либо перемещений. Среднее число перемещений приблизительно равно n /2 * log(n), причем отклонения от этого значения относительно невелики.