Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди 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), причем отклонения от этого значения относительно невелики.