Сравнение эффективности методов сортировки массивов

получаем, наконец, приблизительное значение M_avg = n(ln (n) + g)

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

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

Метод сортировки с помощью прямого выбора ос­нован на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n —1 элемен­тов и т. д. Обнаружение наименьшего среди п эле­ментов требует—это очевидно — n — 1 сравнения, среди n — 1 уже нужно n — 2 сравнений и т. д. Сумма первых n — 1 целых равна 1/2*(n² — n). Как же в та­ком случае можно усовершенствовать упомянутый ме­тод сортировки? Этого можно добиться, только остав­ляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С по­мощью n/4 сравнений — меньший из пары уже вы­бранных меньших и т. д. Проделав n — 1 сравнений, мы можем построить дерево выбора вроде представ­ленного на рис. 2,3 и идентифицировать его корень как нужный нам наименьший ключ [2.21.

Второй этап сортировки — спуск вдоль пути, отме­ченного наименьшим элементом, и исключение его из дерева путем замены либо на пустой элемент (дырку) в самом низу, либо на элемент из соседней ветви в промежуточных вершинах (см. рис. 2.4 и 2.5). Элемент, передвинувшийся в корень дерева, вновь бу­дет наименьшим (теперь уже вторым) ключом, и его можно исключить. После п таких шагов дерево станет пустым (т. е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внима­ние — на каждом из n шагов выбора требуется только log n сравнений. Поэтому на весь процесс понадобит­ся порядка n*log n элементарных операций плюс еще n шагов на построение дерева. Это весьма суще­ственное улучшение не только прямого метода, тре­бующего п² шагов, но и даже метода Шелла, где нужно п^1.2 шага. Естественно, сохранение дополни­тельной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Ведь в конце концов для сохране­ния избыточной информации, получаемой при начальном проходе, создается некоторая древообраз­ная структура. Наша следующая задача — найти приемы эффективной организации этой информации.

Конечно, хотелось бы, в частности, избавиться от дырок, которыми в конечном итоге будет заполнено все дерево и которые порождают много ненужных сравнений. Кроме того, надо было бы поискать такое представление дерева из п элементов, которое требует лишь п единиц памяти, а не 2n—1, как это было раньше. Этих целей действительно удалось добиться в методе Heapsort¹*) изобретенном Д. Уилльямсом (2.14), где было получено, очевидно, существенное улучшение традиционных сортировок с помощью де­ревьев. Пирамида определяется как последователь­ность ключей h_i., h_L+1, .. , h_r, такая, что

Если любое двоичное дерево рассматривать как мас­сив по схеме на рис. 2.6, то можно говорить, что де­ревья сортировок на рис. 2.7 и 2.8 суть пирамиды, а элемент h1, в частности, их наименьший элемент: hi==min(hi, h2, ..., hn). Предположим, есть некото­рая пирамида с заданными элементами h_L+1, ..., h_R для некоторых значений L и R и нужно добавить но­вый элемент х, образуя расширенную пирамиду h_i., .. . ..., l_i R. Возьмем, например, в качестве исходной пи­рамиду hi, ..., hr, показанную на рис. 2.7, и добавим к ней слева элемент h₁==44² Новая пирамида по­лучается так: сначала х ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значе­ние 44 сначала меняется местами с 06, затем с 12 ц в результате образуется дерево, представленное на рис. 2.8. Теперь мы сформулируем этот сдвигающий алгоритм так: i, j — пара индексов, фиксирующих эле­менты, меняющиеся на каждом шаге местами. Чита­телю остается лишь убедиться самому, что предложен­ный метод сдвигов действительно сохраняет неизмен­ным условия (2.13), определяющие пирамиду.

Р. Флойдом был предложен некий «лаконичный» способ построения пирамиды «на том же месте». Его процедура сдвига представлена как прогр. 2.7. Здесь hi . .. hn — некий массив, причем Ьщ ...hn (пп = ==(nDIV2)+1) уже образуют пирамиду, поскольку индексов i, j, удовлетворяющих отношениям j = 2i (или j = 2i+1), просто не существует. Эти элементы образуют как бы нижний слой соответствующего двоичного дерева (см. рис. 2.6), для них никакой

PROCEDURE sift(L, R; index);

VAR i, j: index; x: item;

BEGIN i : = L; J:= 2*L; x := a[L];

IF (j < R) & (a[J+l] < a[j] THEN j:=j+l END;

WHILE (j < =R)&(a[j]

a[i]:= a[j]: i:=j; i := 2*j;

IF(j

END

END sift

Прогр. 2.7. Sift.

упорядоченности не требуется. Теперь пирамида рас­ширяется влево; каждый раз добавляется и сдвигами ставится в надлежащую позицию новый элемент. Табл. 2.6 иллюстрирует весь этот процесс, а получаю­щаяся пирамида показана на рис. 2.6.

Следовательно, процесс формирования пирамиды из п элементов hi ... hn на том же самом месте опи­сывается так:

L :== (n DIV 2) + 1;

WHILE L > 1 DO L :== L — 1; sift(L, n) END

Для того чтобы получить не только частичную, но и полную упорядоченность среди элементов, нужно про­делать n сдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший) элемент. И вновь возникает вопрос: где хранить «всплывающие» верхние элементы и мож­но ли или нельзя проводить обращение на том же месте? Существует, конечно, такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х), прятать верхний элемент пирамиды в освободившемся теперь месте, а х сдвигать в нужное место. В табл. 2.7 приведены необходимые в этом слу-

.Таблица 2.6, Построение пирамиды

Таблица 2.7. Пример процесса сортировки с помощью Heapsort

чае n — 1 шагов. Сам процесс описывается с помощью процедуры sift (прогр. 2.7) таким образом:

R:=n; WHILE R>1 DO х := а[l]; a[l] := a[R]; a[R] := x: R:=R-l; sift(l,R) END

Пример из табл. 2.7 показывает, что получающийся порядок фактически является обратным. Однако это можно легко исправить, изменив направление «упо­рядочивающего отношения» в процедуре sift. В конце концов получаем процедуру Heapsort (прогр. 2.8),

PROCEDURE HeapSort; VAR L, R: index; х: item; PROCHDURE sift(L, R: index); VAR i,j:index; x: item; BEGIN i: = L; j := 2*L: x := a[L]; IF(j < R) & (a[j] < a[j+1]) THEN j := j+l END; WHILE(j<=R)&(x

BEGIN L:=:(nDIV2)+l:R:=n; WHILE L > 1 DO L: = L-l; sift(L, R) END; WHILER>1 DO x := a[l]; a[l] := a[R]; a[R] := x; R := R-l; sifl(L, R) END END HeapSort

Прогр. 2.8. HeapsorL

Анализ Heapsort. На первый взгляд вовсе не оче­видно, что такой метод сортировки дает хорошие ре­зультаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. И действительно, про­цедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для боль­ших же n Heapsort очень эффективна; чем больше п, тем лучше она работает. Она даже становится срав­нимой с сортировкой Шелла.

В худшем случае нужно п/2 сдвигающих шагов, они сдвигают элементы на log (n/2), log (п/2—1), ... ..., log(n—l) позиций (логарифм (по основанию 2)] «обрубается» до следующего меньшего целого). Сле­довательно, фаза сортировки требует n—1 сдвигов с самое большое log(n—1), log(n—2), ..., 1 переме­щениями. Кроме того, нужно еще n —1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heap-sort потребует n*log n шагов. Великолепная произ­водительность в таких плохих случаях—одно из при­влекательных свойств Heapsort.

Совсем не ясно, когда следует ожидать наихудшей (или наилучшей) производительности. Но вообще-то кажется, что Heapsort «любит» начальные последо­вательности, в которых элементы более или менее отсортированы в обратном порядке. Поэтому ее по­ведение несколько неестественно. Если мы имеем дело с обратным порядком, то фаза порождения пирамиды не требует каких-либо перемещений. Среднее число перемещений приблизительно равно п/2* log(n), при­чем отклонения от этого значения относительно неве­лики.