Реферат: Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева

M_max = n² /4 +3(n-1)

если первоначально ключи располагались в обратном порядке. Для того чтобы определить Mavg, мы должны рассуждать так. Алгоритм просматривает массив, сравнивая каждый элемент с только что обнаружен­ной минимальной величиной; если он меньше первого, то выполняется некоторое присваивание. Вероят­ность, что второй элемент окажется меньше первого, равна 1/2, с этой же вероятностью происходят при­сваивания минимуму. Вероятность, что третий эле­мент окажется меньше первых двух, равна 1/3, а ве­роятность для четвертого оказаться наименьшим — 1/4 и т. д. Поэтому полное ожидаемое число пересы­лок равно Нn—1, где Нn — n-е гармоническое число:

Нn=1+1/2+1/3+ ... +1/nНп можно выразить и так: Нп = In n+g+ 1/2n — 1/12n² + ...

где g= 0.577216 ... — константа Эйлера. Для доста­точно больших n мы можем игнорировать дробные составляющие и поэтому аппроксимировать среднее число присваиваний на i-м просмотре выражением

F_i -ln i+g+l

Среднее число пересылок Mavg в сортировке с вы­бором есть сумма Fi с i от 1 до n:

M_avg =n*(g+l)+(S_i : 1<i

Вновь аппроксимируя эту сумму дискретных членов интегралом Integral (1: п) ln x dx == x * (ln x— 1) == n * ln (п)— n + I

получаем, наконец, приблизительное значение 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<R)&(a[j+1]

END

END sift

Прогр. 2.7. Sift.

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

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

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