Реферат: Быстрые алгоритмы сортировки

A[i] ³ A[2*i], A[i] ³ A[2*i+1]

а потім змінює місцями A[1] (найбільший елемент) і A[n].

Як і TreeSort, алгоритм HeapSort працює в два етапи:

I. Побудова сортуючого дерева;

II. Просівання елементів по сортуючому дереву.

Дерево, що представляє масив, називається сортуючим, якщо виконуються умови (6). Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.

Як на I-ом, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура ConSwap).

У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. (На мал шлях вирішення конфлікту роду у вершині 2 відзначений). Конфлікт роду вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий сімейний конфлікт (процедура Conflict).

Procedure ConSwap(i, j : Integer);

Var b : Real;

Begin

If a[i] < a[j] then begin

b := a[i]; a[i] := a[j]; a[j] := b

end

End;

Procedure Conflict(i, k : Integer);

Var j : Integer;

Begin

j := 2*i;

If j = k

then ConSwap(i, j)

else if j < k then begin

if a[j+1] > a[j] then j := j + 1;

ConSwap(i, j); Conflict(j, k)

end

End;

I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:

Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) є сортуючими, то для перебудови T(i) необхідно вирішити конфлікт роду в цьому дереві.

Procedure SortTree(i : Integer);