|
Таблица 2.7. Пример процесса сортировки с помощью Heapsort
06
42
12
55
94
18
44
67
12
42
18
55
94
67
44
06
18
42
44
55
94
67
12
06
42
55
44
67
94
18
12
06
44
55
94
67
42
18
12
06
55
67
94
44
42
18
12
06
67
94
55
44
42
18
12
06
94
67
55
44
42
18
12
06
чае 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<a[j])DO a[i]:=a[j]; i :=j: j:=2*j: IF(J<R)&(a[i]<a[j+l]) THENj:=j+1 END END END sift;
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), причем отклонения от этого значения относительно невелики.
[1] Здесь мы оставляем попытки перевести названия соответствующих методов на русский язык, ибо ни уже не более чем собственные имена, хотя в названиях первых упоминавшихся методов еще фигурировал некоторый элемент описания сути самого приема сортировки. — Прим. перев.
[2] Это несколько противоречит утверждению, что lu+i ..) ...hr—пирамида, но надеемся, сам читатель разберется, Что хотел сказать автор. — Прим. перев.
Страницы: 1, 2
При использовании материалов активная ссылка на источник обязательна.