ПОШУК, СОРТУВАННЯ ТА ПОНЯТТЯ СКЛАДНОСТІ У ПРОГРАМУВАННІ

end

end

end

Після виконання виклику reorg( A, i, j ) за будь-якого i
procedure bld (var A : ArT; n : Indx );

var i : Indx;

begin

for i := n div 2 downto 1 do reorg ( A, i, n )

end

Оцінимо складність алгоритму. За наведеними процедурами очевидно, що складність алгоритму прямо пропорційна загальній кількості викликів процедури reorg. При виконанні процедури bld процедура reorg викликається ndiv2 разів, а при виконанні циклу for процедури Treesort – ще n-2 рази. Отже, загальна кількість викликів процедури reorg з інших процедур є O(n). Кількість елементарних дій при виконанні операторів її тіла оцінюється сталою, тобто O(1). У кожному рекурсивному виклику процедури reorg значення її другого параметра не менше ніж подвоюється, тому кожний виклик reorg з інших процедур породжує не більше O(logn) рекурсивних викликів. Звідси випливає, що загальна кількість елементарних дій є O(nlogn).

4.3. Швидке сортування

Ідея швидкого сортування така. Певним чином вибирається значення v. Значення елементів масиву A обмінюються так, що елементи на його початку мають менші від v значення, а від деякого місця k значення елементів більші або рівні v. Це значення називається відокремлюючим; воно знаходиться на своєму місці, якщо A[k]=v. Після розміщення відокремлюючого значення на потрібному місці достатньо окремо відсортувати частини масиву від A[1] до A[k-1] та від A[k+1] до кінця.

Нехай діють означення (17.1). Сортування частини масиву A[lo] … A[hi] з відокремлюючим значенням A[lo] задається такою процедурою:

procedure quicksort ( A : ArT; lo, hi : Indx ) ;

var k, j : Indx; v : T;

label 1;

begin

if lo >= hi then goto 1;

if (lo = hi - 1) and (A[lo] > A[hi]) then

begin