Швидкі алгоритми сортування

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);

begin

If i <= n div 2 then begin

SortTree(2*i); SortTree(2*i+1); Conflict(i, n)

end

end;

На II-ом етапі - етапі просівання - для k від n до 2 повторюються наступні дії:

1.Переставити A[1] і A[k];

2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.

Program HeapSort;

Const n = 100;

Var A : Array[1..n] of real;

k : Integer;

{процедури ConSwap, Conflict, SortTree, введення, виведення}