Пошук, сортування та поняття складності у програмуванні, Детальна інформація

procedure Treesort ( var a : ArT; n : Indx );

var j : Indx;

begin

bld (A, n);

for j := n downto 3 do

begin

swap (A[1], A[j]); reorg (A, 1, j-1)

end

end

Властивість (17.2) відновлюється в частині масиву A[1], … , A[n-1] таким чином. Обмінюються значення A[1] та того з A[2] або A[3] (позначимо його A[k]), чиє значення максимальне. У результаті властивість (17.2) може порушитися в частині масиву A[k], … , A[n-1]. У ній відновлення відбувається так само, як і серед A[1], … , A[n-1].

Опишемо відновлення частини масиву A[i], … , A[j] у загальному випадку значень i, j. Нехай у частині масиву A[i], … , A[j], де 2*i+1\xF0A3 j, треба відновити властивість (17.2), можливо, порушену з початку: A[i]A[2*i+1] покладемо k=2*i, у противному разі – k=2*i+1. Обміняємо значення A[i] та A[k]; після цього, якщо необхідно, властивість (17.2) відновлюється в частині масиву A[k], … , A[j].

Коли 2*i=j, то лише порівнюються й, можливо, обмінюються значеннями A[i] та A[j], причому k=j.

Коли 2*i>j, то властивість (17.2) не може бути порушеною в частині масиву A[i], … , A[j].

За дії означень (17.1) відновлення задається рекурсивною процедурою reorg:

procedure reorg ( var A : ArT; i, j : Indx );

var k : Indx;

begin

if 2*i = j then

if A[i] < A[j] then swap ( A[i], A[j] );

if 2*i < j then

begin

if A[2*i] > A[2*i+1] then k := 2*i

else k := 2*i + 1;

if A[i] < A[k] then

begin

swap ( A[i], A[k] ); reorg ( A, k, j )

end

end

end

Після виконання виклику reorg( A, i, j ) за будь-якого i