WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Пошук, сортування та поняття складності - Реферат

Пошук, сортування та поняття складності - Реферат

вузла k, який називається їхнім батьком. Вузол 1 називається вершиною піраміди. Кожний вузол також можна вважати вершиною піраміди, складеної ним, його синами, їх синами тощо. Наприклад, вузол 2 є вершиною піраміди, складеної з 2, 4, 5, 8, 9, 10, 11, вузол 3 - піраміди з 3, 6, 7, 12.
Піраміду можна розглядати як дерево, гілки якого - стрілки від батьків до синів. Вершина піраміди називається коренем дерева.
Припустимо тепер, що значення елементів масиву розташовано так, що значення кожного елемента-батька не менше значень його синів:
A[1] A[2] та A[1] A[3], A[2] A[4] та A[2] A[5] тощо.
Отже, за кожного k=1, 2, … , n div 2
A[k] A[2*k] та A[k] A[2*k+1] (17.2)
(за парного n елемент A[n div 2] має лише одного сина A[n]). Наприклад,
30
12 30
12 5 29 2
11 10 3 2 28 27
Цій піраміді відповідає послідовне розташування .
Очевидно, що кожний елемент має значення, найбільше в тій піраміді, де він є вершиною. Наприклад, A[2] має значення, найбільше серед елементів із індексами 2, 4, 5, 8, 9, 10, 11. Зокрема, A[1] має значення, найбільше серед усіх елементів.
Якщо помінятимісцями значення A[1] і A[n], то елемент A[n] матиме найбільше значення. Про нього "можна забути" та зосередитися на сортуванні A[1], A[2], ... , A[n-1]. Зрозуміло, що умова A[1] A[2], A[1] A[3] після обміну може виявитися порушеною. Для її відновлення треба обміняти місцями значення A[1] та того з A[2], A[3], чиє значення максимальне. Нехай це буде A[3]. В останньому прикладі після обміну значень A[1] і A[12] на вершині піраміди значення 27, і 27<30, тобто A[1]Після відновлення умови (17.2) можна буде обміняти значення першого елемента з передостаннім, "забути" про нього, знову відновити умову, знову загнати перше значення в кінець тощо.
Нехай процедура bld(A, n) задає початкову перестановку значень масиву таким чином, що виконується умова (17.2), а процедура reorg(A, i, k) - її відновлення у частині масиву A[i], … , A[k]. Тоді за дії означень (17.1) сортування задається процедурою Treesort:
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 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 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= 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 k := k - 1;
{ A[k] є останнім від початку елементом, }
{ значення якого менше v }
swap ( A[lo], A[k] ); { A[k] = v }
quicksort ( A , lo, k - 1 );
quicksort ( A , k + 1, hi );
1: end
Якщо за виконання кожного виклику після циклу while значення змінної k приблизно рівне (lo+hi)/2, то складність швидкого сортування масиву з n елементів можна оцінити як O(nlogn). Середня кількість порівнянь елементів усіх можливих числових послідовностей довжини n також має оцінку O(nlogn); доведення є, наприклад, у книзі [АХУ]. Емпіричні дослідження свідчать, що швидке сортування вимагає в середньому елементарних дій приблизно вдвічі менше, ніж сортування деревом, і вчетверо менше, ніж сортування злиттям. Але якщо початковий масив близький до відсортованого, то його сортування за наведеним алгоритмом вимагає вже O(n2) порівнянь. У такому випадку відокремлюючим елементом не можна вибирати значення A[lo].
Існує багато способів вибору іншого відокремлюючого значення. Наприклад, можна вибрати значення елемента з випадковим номером серед номерів lo, … , hi, або середнє із значень A[lo], A[hi], та A[(lo+hi)div2]. У такому разі перед оператором процедури
v := A[lo]; {?!}
треба задати обмін значень A[lo] та відповідного елемента, чиє значення вибирається відокремлюючим.
5. Відсортуй, і багато чого побачиш
Вам треба огородити сад із деревами, витративши на огорожу якомога менше матеріалу. Вважатимемо, що дерев не менше трьох, і вони задаються координатами на площині. Розв'язання полягає в побудові так званої опуклої оболонки навколо множини точок із заданими координатами. На площині вона являє собою опуклий багатокутник, що містить усі задані точки і не містить інших опуклих багатокутників, які також "накривають" усі точки.
Якщо намалювати план саду, то побудова оболонки стане очевидною. Треба відшукати якусь "крайню" початкову точку і рухатися від неї, малюючи опуклий багатокутник. Як результат, ми одержимо послідовність вершин - заданих точок, на які "натягнуто" багатокутник. Точки, що потрапили на сторону багатокутника, але не є вершинами, можна відкинути.
Наприклад, за множини точок із координатами (1,1), (2,2), (3,3), (5,-1), (2,-1), (3,0) ми одержимо багатокутник із вершинами (1,1), (3,3), (5,-1), (2,-1). Точка (3,0)
Loading...

 
 

Цікаве