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

Пошук, сортування та поняття складності
Тип документу: Реферат
Сторінок: 13
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 35.2
Скачувань: 944
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
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

The online video editor trusted by teams to make professional video in minutes