Сортування простими вставками
Сортування простими вставками дозволяє створити відсортований масив із значень, що читаються, наприклад, із клавіатури. Перше значення записується на перше місце, тобто присвоюється першому елементу масиву. Друге значення порівнюється з першим і, якщо перше менше, то воно "витісняється" на друге місце. Інакше нове значення йде на друге місце. Потім третє порівнюється з другим та записується або на третє місце, або витісняє значення з другого місця на третє та порівнюється з тим, що на першому місці. Наприклад, за читання послідовності значень 3, 1, 2 створюються послідовності значень у масиві <3>, <1, 3>, <1, 2, 3>. Узагалі, після читання k-1 елемента маємо відсортовану частину масиву A[1]A[2].A[k-1]. Нове значення v порівнюємо зі значенням A[k-1]. Якщо A[k-1]>v, то значення A[k-1] зсуваємо на k-е місце. Після цього порівнюємо v зі значенням A[k-1]: якщо A[k-2]>v, то A[k-2] зсуваємо на (k-1)-е місце тощо. Коли за чергового порівняння A[i]<=v, то v записується на (i+1)-е місце. Якщо всі значення в масиві більші v, то вони зсуваються, а v записується на перше місце. Уточнити наведений алгоритм процедурою.
2.6. Ефективні алгоритми сортування. Сортування злиттям В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової. Нехай у масиві Y з елемента Y[m] починається впорядкована ділянка довжиною s, а з елемента Y[m+s] – впорядкована ділянка довжини r. Наприклад,
Результатом злиття повинна бути ділянка довжини r+s у масиві X:
За дії означень (17.1) таке злиття двох ділянок у масиві Y у ділянку масиву X задає процедура procedure mrg(var Y: ArT; m, s, r: Indx; var X: ArT); var mr, k: Indx; i, j: Extind; begin mr:= m + s; { mr – початок правої частини } i:= m; j:= mr; { i та j пробігають ліву й праву ділянки масиву Y} for k:= m to m + s + r - 1 do{заповнення X[m], …, X[m+s+r-1]} if i > m + s - 1 then begin X[k]:= Y[j]; j:= j + 1 end else if j > mr + r - 1 then begin X[k]:= Y[i]; i:= i + 1 end else if Y[i] < Y[j] then begin X[k]:= Y[i]; i:= i + 1 end else begin X[k]:= Y[j]; j:= j + 1 end end Тепер розглянемо сортування масиву A злиттям. На першому кроці елементи A[1], …, A[n] копіюються в допоміжний масив B[1], …, B[n]. Його елементи розглядаються парами B[1] і B[2], B[3] і B[4] тощо як упорядковані послідовності довжиною lp = 1 і зливаються за допомогою процедури mrg в масив A. Тепер там є впорядковані ділянки довжиною 2. За непарного n останній елемент A[n] залишається без змін як послідовність довжиною 1. На наступному кроці після копіювання в масив B зливаються пари упорядкованих ділянок B[1]B[2] і B[3]B[4], B[5]B[6] і B[7]B[8] тощо. З'являються впорядковані ділянки довжиною 4. Нехай t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t. Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n. Розглянемо сортування злиттям масиву <11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> довжини n=11. Упорядковані послідовності в ньому вказуються в дужках <>, а пари таких, що зливаються, відокремлені ";": < <11><10>; <9><8>; <7><6>; <5><4>; <3><2>; <1> >, lp=1 < <10, 11><8, 9>; <6, 7><4, 5>; <2, 3><1> >, lp=2 < <8, 9, 10, 11><4, 5, 6, 7>;<1, 2, 3> >, lp=4 < <4, 5, 6, 7, 8, 9, 10, 11><1, 2, 3> >, lp=8 <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp³ n. Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив. За дії означень (17.1) такий спосіб сортування описується процедурою Mrgsort: procedure Mrgsort (var A: ArT; n: Indx); var B: ArT; lp, npp, cpp, bpp, tl: integer; begin lp:= 1; while lp < n do begin B:= A; { копіювання } 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 у 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 році його винайшов Джон фон Нейман, один із піонерів програмування. Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Розглянемо два алгоритми, позбавлені цього недоліку.
2.7. Пірамідальне сортування
Піраміда, вона ж дерево Уявіть собі, що ми розташували елементи масиву рядками, щоразу подвоюючи їх кількість: у першому рядку – перший елемент, у другому – елементи з індексами 2, 3, у наступному – 4, 5, 6, 7, далі 8, 9, 10, 11, 12, 13, 14, 15 тощо. Останній рядок може виявитися неповним. Наприклад, за кількості елементів n=12 маємо таку піраміду індексів: 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] (за парного n елемент A[n div 2] має лише одного сина A[n]). Наприклад, 12 30 12 5 29 2 11 10 3 2 28 27 Цій піраміді відповідає послідовне розташування <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]<A[3]. Після обміну їх значень умова може порушитися в піраміді з вершиною A[3]. Відновимо цю умову так само, як і для вершини A[1], опустившися при цьому до вузла A[6] чи A[7]. І так далі. Після відновлення умови можна буде обміняти значення першого елемента з передостаннім, "забути" про нього, знову відновити умову, знову загнати перше значення в кінець тощо. Нехай процедура bld(A, n) задає початкову перестановку значень масиву таким чином, що виконується умова, а процедура reorg(A, i, k) – її відновлення у частині масиву A[i], …, A[k]. Тоді за дії означень сортування задається процедурою 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 Властивість відновлюється в частині масиву A[1], …, A[n-1] таким чином. Обмінюються значення A[1] та того з A[2] або A[3] (позначимо його A[k]), чиє значення максимальне. У результаті властивість може порушитися в частині масиву A[k], …, A[n-1]. У ній відновлення відбувається так само, як і серед A[1], …, A[n-1]. Опишемо відновлення частини масиву A[i], …, A[j] у загальному випадку значень i, j. Нехай у частині масиву A[i], …, A[j], де 2*i+1£ j, треба відновити властивість, можливо, порушену з початку: A[i]<max{A[2*i], A[2*i+1]}. За умови A[2*i]>A[2*i+1] покладемо k=2*i, у противному разі – k=2*i+1. Обміняємо значення A[i] та A[k]; після цього, якщо необхідно, властивість відновлюється в частині масиву A[k], …, A[j]. Коли 2*i=j, то лише порівнюються й, можливо, обмінюються значеннями A[i] та A[j], причому k=j. Коли 2*i>j, то властивість не може бути порушеною в частині масиву A[i], …, A[j]. За дії означень відновлення задається рекурсивною процедурою 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 < 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<jdiv2 елемент A[i] має максимальне значення серед A[i], A[2*i], A[2*i+1]. Цим можна скористатися для побудови початкового масиву з властивістю: спочатку "відновлюється" частина масиву A[ndiv2], …, A[n], потім частина A[ndiv2-1], …, A[n] тощо. Звідси процедура bld: 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).
|
