Сторінка
5
30
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]. Після обміну їх значень умова (17.2) може порушитися в піраміді з вершиною A[3]. Відновимо цю умову так само, як і для вершини A[1], опустившися при цьому до вузла A[6] чи A[7]. І так далі. Після відновлення умови (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]<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]; після цього, якщо необхідно, властивість (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 < 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]. Цим можна скористатися для побудови початкового масиву з властивістю (17.2): спочатку "відновлюється" частина масиву 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). 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; { 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] та відповідного елемента, чиє значення вибирається відокремлюючим. Задачі 8. Переробити процедуру Merges так, щоб на кроці з непарним номером перший масив без копіювання зливався в другий, а на кроці з парним номером, навпаки, другий без копіювання зливався в перший. 9.* Написати нерекурсивний варіант сортування деревом (підр.17.4.2). 10. За масивом із N рядків визначається додатковий індексовий масив: попаpно pізні значення його елементів належать діапазону 1 N і є індексами в масиві рядків. Написати процедуру а) сортування індексового масиву таким чином, щоб рядки, на які посилаються його послідовні елементи, були лексикогpафічно впоpядковані; б) друкування рядків масиву за зpостанням у лексикографічному порядку (кожний рядок друкується один pаз незалежно від кількості повтоpень у масиві). 11. Написати процедуру обчислення N (N £ 1000) найменших значень числової послідовності довільної довжини за умови, що а)* незалежно від кількості повтоpень усі числа враховуються один pаз кожне; б) число враховується стільки pазів, скільки воно зустрілося в послідовності (але не більше ніж N); в) числа враховуються один pаз кожне, але ведеться додатковий облік кількостей їх повтоpень. 12. Запрограмувати злиття а) трьох б) п'яти в) тисячі упорядкованих послідовностей в одну. 13.* Запрограмувати сортування елементів зв'язаного списку. Складність алгоритму повинна бути O(nlogn). 14. Запрограмувати сортування послідовностей із а) чотирьох елементів так, щоб виконувалося не більше п'яти порівнянь; б) п'яти елементів так, щоб виконувалося не більше восьми порівнянь; в) п'яти елементів так, щоб виконувалося не більше семи порівнянь.
Завантажити реферат