Пошук, сортування та поняття складності у програмуванні, Детальна інформація
Пошук, сортування та поняття складності у програмуванні
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
swap ( A[lo], A[hi] );
goto 1
end;
k := lo + 1; j := hi;
v := A[lo]; {?!}
while ( k < j ) do
if A[k] < v then k := k + 1
else
begin
if A[j] < v then swap ( A[k], A[j] );
j := j - 1
end;
{ k = j }
if A[k] >= v then k := k - 1;
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
swap ( A[lo], A[hi] );
goto 1
end;
k := lo + 1; j := hi;
v := A[lo]; {?!}
while ( k < j ) do
if A[k] < v then k := k + 1
else
begin
if A[j] < v then swap ( A[k], A[j] );
j := j - 1
end;
{ k = j }
if A[k] >= v then k := k - 1;
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021