Сторінка
4

Пошук, сортування та поняття складності у програмуванні

npp := n div (2*lp); { кількість пар ділянок } tl := n mod (2*lp); { довжина залишку } for cpp := 1 to npp do { cpp – номер пари } begin bpp := (cpp - 1)*2*lp + 1;

{ індекс першого елемента лівої ділянки пари} mrg ( B, bpp, lp, lp, A );

end; { обробка залишку } if tl > lp then mrg ( B, n - tl + 1, lp, tl - lp, A ); { за tl <= lp залишок був упорядкований } { на попередньому кроці } lp := lp*2 end { lp >= n : масив упорядковано на останньому кроці } end Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1<n, то при виконанні останнього кроку мають місце співвідношення lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp, і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив. Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+ë log2nû =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn). Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+ë log2nû ) та округлене відношення r двох останніх:

n	n(n-1)/2	n(1+ë log2nû)	r
10	45	40	1
100	4950	700	7
1000	499500	10000	50
10000	49995000	140000	350

Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+ë log2nû ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове! Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою. Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний: procedure Mrgrec(var A, B : ArT; l, r : integer); var m, k : integer; begin if l>=r then exit; m:=(l+r) div 2; Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r); mrg(A, l, m-l+1, r-m, B); for k:=l to r do A[k]:=B[k]; end; Ця процедура набагато коротше нерекурсивної процедури Merges, але виконання її довше. Власне сортування починається лише після повернення з викликів, у яких l=r, а це практично "середина дистанції". Завершуючи описання сортування злиттям, скажемо, що цей алгоритм є першим із ефективних алгоритмів сортування. У 1945 році його винайшов Джон фон Нейман, один із піонерів програмування. Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Розглянемо два алгоритми, позбавлені цього недоліку. 4.2. Піраміда, вона ж дерево Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним. Наприклад, за кількості елементів n=12 маємо таку піраміду індексів:

1

2 3

4 5 6 7

8 9 10 11 12 Елементи цієї піраміди будемо називати вузлами. Між вузлами проведемо стрілки: від 1 – до 2 та 3, від 2 – до 4 та 5, від 3 – до 6 та 7 тощо, тобто від кожного вузла k до 2k та 2k+1, де k<n div 2 (рис.17.1). За парного n від вузла (n div 2) проводиться стрілка лише до вузла n. Вузли 2k та 2k+1 називаються синами вузла 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]). Наприклад,