p align="left">Теорема. Якщо k-відсортовану послідовність i-відсортувати, то вона при цьому залишиться k-відсортованою. Кнут рекомендує використовувати такі послідовності відстаней, записані в зворотньому порядку : 1, 4, 13, 40, 121, ... , де h i-1=3h i+1 , h t=1 , t=[log 3 N]-1 , або 1, 3, 7, 15, 31, ... , де h i-1=2h i+1 , h t=1 , t=[log 2 N]-1. З обчислювальної практики відомо, що загалом метод Шелла має ефективність порядку O(N1,2). 2.2 Сортування обміном на великих відстанях - алгоритм Quick Sort Основна причина повільної роботи алгоритму прямого обміну полягає в тому, що всі порівняння і перестановки елементів в послідовності a 1 , a 2 , ..., a N відбуваються для пар із сусідніх елементів. При такому способі потрібно відносно більше часу, щоб поставити деякий ключ, який знаходиться не на своєму місці, в потрібну позицію у сортованій послідовності. Природньо попробувати пришвидшити цей процес, порівнюючи пари елементів, що знаходяться далеко один від одного в масиві. К. Хоор розробив алгоритм Quick Sort із середнім часом роботи порядку O(N*lnN). Припустимо, що перший елемент масиву, що сортується, є хорошим наближенням елемента, який вкінці опиниться на своєму місці у відсортованій послідовності. Приймемо його значення в якості ведучого елемента, відносно якого ключі будуть мінятися місцями. Для зручності реалізації алгоритму використаємо два вказівники I, J, перший з яких вестиме відлік вздовж розглядуваної частини масиву зліва, а другий - справа. Початково їх значення будуть відповідно I=1, J=N. Таким чином ведучим елементом буде значення a[I]. Перестановки ключів проводяться за такими принципами : 1) порівнюються елементи a[I] та a[J]; якщо a[I]a[J], то здійснюється крок вліво J:=J-1 і порівняння повторюється; зменшення J продовжується доти, поки не виконається умова a[I]> a[J]; 2) якщо при порівнянні елементів досягнута умова a[I]> a[J], то проводиться обмін місцями кючів a[I] та a[J] і здійснюється крок вправо I:=I+1; таким чином ведучий елемент перейшов в позицію J; порівняння ключів із збільшенням I продовжується доти, поки знову не виконається умова a[I]> a[J]; 3) у випадку виконання умови a[I]> a[J] проводиться обмін місцями кючів a[I] та a[J] і здійснюється крок вліво J:=J-1; при цьому ведучий елемент знову повертається в позицію I. Цей процес із почерговим зменшенням J та збільшенням I повторюється з обох кінців послідовності до "середини"до тих пір, поки не досягнеться I=J. Тепер мають місце два факти. По-перше, ключ, що був першим у вихідній послідовності, в результаті такого впорядкування опиняється на "своєму" місці. По-друге, всі елементи зліва будуть меншими за нього, а всі ключі справа - більшими. Ту ж саму процедуру можна використати для впорядкування лівої і правої підпослідовностей і т. д. до повного сортування всьго масиву. Таким чином розглянутий алгоритм має чітко виражений рекурсивний характер. Виходячи з цього, значення індексів крайніх елементів меншої з двох невідсортованих підпослідовностей варто помістити в стекову структуру даних, і приступити до впорядкування більшої підпослідовності. Оскільки короткі послідовності скоріше сортуються при допомозі прямих методів, то алгоритм Quick Sort матиме вхідний параметр - деяке число S, що визначає нижню межу його використання. Провівши нескладний математичний аналіз нерівності, яка пов'язує ефективності алгоритму Quick Sort та прямих алгоритмів сортування , можна встановити значення числа S, яке буде нижньою межею використання швидкого сортування. Остання нерівність дає результат . Однак, якщо крім основних операцій порівняння ключів ще враховувати порівняння індексів та перестановки елементів, то це значення можна збільшити в 2-3 рази. В якості прикладу наводиться програмна реалізація цього алгоритму у вигляд процедури Quick_Sort. В ній використовується два масиви left і right, де зберігатимуться індексні номери відповідно лівої і правої границь підпослідовностей, які ще будуть впорядковуватися на наступних етапах. Procedure Quick_Sort; Const S=20; Var k, L, R, i, j : integer; x : basetype; left, right : array [1..N] of integer; Begin k:=1; left[k]:=1; right[k]:=N; while k>0 do begin L:=left[k]; R:=right[k]; k:=k-1; while R-L>S do begin i:=L; j:=R; x:=a[i]; while j>i do begin while x<a[j] do j:=j-1; if j>i then begin a[i]:=a[j]; a[j]:=x; i:=i+1 end; while a[i]<x do i:=i+1; if j>i then begin a[j]:=a[i]; a[i]:=x; j:=j-1 end end; k:=k+1; if R-i<=i-L then begin left[k]:=i+1; right[k]:=R; R:=i-1 end else begin left[k]:=L; right[k]:=i-1; L:=i+1 end end; for i:=L+1 to R do begin x:=a[i]; j:=i-1; while (x<a[j]) and (j>=L) do begin a[j+1]:=a[j]; j:=j-1 end; a[j+1]:=x end end End; Аналіз алгоритму Quick Sort. Щоб оцінити ефективність алгоритму, позначимо через Q(N) середню кількість кроків, необхідних для впорядкування N елементів. Припустимо також, S=1, тобто не використовується сортування прямими методами на коротких послідовностях. При першому проходженні Quick Sort порівнює всі елементи з ведучим і виконується не більше ніж за C*N кроків, де C - деяка константа. Потім потрібно відсортувати дві підпослідовності довжинами I-1 та N-I. Тому середня кількість кроків, потрібних для впорядкування N елементів, залежить від середньої кількості кроків, потрібних для впорядкування I-1 та N-I елементів відповідно. Оскільки всі можливі значення є рівноймовірними, то спрведлива наступна оцінка : . Врахувавши, що , отримаємо .(1) Покажемо за індукцією по N, що для , де K=2C+2B, B=Q(0)=Q(1). Останнє співвіднощення означає, що Quick Sort вимагає постійної однакової кількості кроків для впорядкування 0 або 1 елемента. 1) N=2 : ; 2) припустимо, що для I=2, 3, ..., N-1 ; 3) перевіримо справедливість для I=N. Співвідношення (1) з врахуванням попереднього припущення можна переписати у вигляді або .(2) Оскільки функція I*ln(I) є опуклою вниз, то для цілих значень аргументу справедлива оцінка Врахувавши останню нерівність, із співвідношення (2) одержимо . Оскільки , то . Остаточно отримаємо .(3) Таким чином ефективність алгоритму Quick Sort є величина порядку O(N*ln(N)). Всі наведені викладки справедливі для аналізу по операціях порівняння. Кількість же перестановок залежить від початкового розміщення елементів у послідовності. Характерно, що для цього методу у випадку зворотньо впорядкованого масиву об'єм переміщень ключів не буде максимальним. Адже на кожному етапі ведучий елемент буде найбільшим і опиниться на своєму місці після першого ж порівняння і перестановки, тобто M=N-1. Максимальна кількість переприсвоєнь ключів співпадатиме з кількістю порівнянь, мінімальна - рівна нулю. Алгоритм Quick Sort, як і розглянуті прямі методи, описує процес стійкого сортування. 2.3 Сортування вибором при допомозі дерева - алгоритм Тree Sort Алгоритм сортування деревом ТreeSort власне кажучи є поліпшенням алгоритму сортування вибором. Процедура вибору найменшого елемента удосконалена як процедура побудови так званого сортуючого дерева. Сортуюче дерево - це структура даних, у якій представлений процес пошуку найменшого елемента методом попарного порівняння елементів, що стоять поруч. Алгоритм сортує масив у два етапи. I етап : побудова сортуючого дерева; II етап : просівання елементів по сортуючому дереву. Розглянемо приклад: Нехай масив A складається з 8 елементів. Другий рядок складається з мінімумів елементів першого рядка, які стоять поруч. Кожний наступний рядок складений з мінімумів елементів, що стоять поруч, попереднього рядка. Ця структура даних називається сортуючим деревом. У корені сортуючого дерева розташований найменший елемент. Крім того, у дереві побудовані шляхи елементів масиву від листів до відповідного величині елемента вузла -розгалуження. Коли дерево побудоване, починається етап просівання елементів масиву по дереву. Мінімальний елемент пересилається у вихідний масив B і усі входження цього елемента в дереві заміняються на спеціальний символ M. Потім здійснюється просівання елемента уздовж шляху, відзначеного символом M, починаючи з листка, сусіднього з M і до кореня. Крок просівання - це вибір найменшого з двох елементів, що зустрілися на шляху до кореня дерева і його пересилання у вузол, відзначений M. a6 = min(M, a6) a6 = min(a6, a8) a3 = min(a3, a6) b2 := a3 Просівання елементів відбувається доти, поки весь вихідний масив не буде заповнений символами M, тобто n раз: For і := 1 to n do begin Відзначити шлях від кореня до листка символом M; Просіяти елемент уздовж відзначеного шляху; B[I] := корінь дерева end; Обґрунтування правильності алгоритму очевидно, оскільки кожне чергове просівання викидає в масив У найменший з елементів масиву А, що залишилися. Сортуюче дерево можна реалізувати, використовуючи або двовимірний масив, або одномірний масиві ST[1..N], де N = 2n-1. Аналіз алгоритму Tree Sort. Оцінимо складність алгоритму в термінах M(n), C(n). Насамперед відзначимо, що алгоритм Tree Sort працює однаково на усіх входах, так що його складність у гіршому випадку збігається зі складністю в середньому. Припустимо, що n - ступінь 2 (n = 2l). Тоді сортуюче дерево має l + 1 рівень (глибину l). Побудова рівня I вимагає n / 2I порівнянь і пересилань. Таким чином, I-ий етап має складність: C1(n) = n/2+n/4+ ... + 2+1 = n-1, M1(n) = C1(n) = n - 1 Для того, щоб оцінити складність II-го етапу С2(n) і M2(n) помітимо, що кожен шлях просівання має довжину l, тому кількість порівнянь і пересилань при просіванні одного елемента пропорційно l. Таким чином, M2(n) = O(l n), C2(n) = O(l n). Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n),остаточно одержуємо оцінки складності алгоритму Tree Sort за часом: M(n) = O(n log2 n), C(n) = O(n log2 n), У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. "Зайвий" елемент (елемент, для якого немає пари) переноситься на наступний рівень. Легко бачити, що при цьому глибина сортуючого дерева дорівнює [log2 n] + 1. Удосконалення алгоритму II етапу очевидно. Оцінки при цьому змінюють лише мультиплікативні множники. Алгоритм Tree Sort має істотний недолік: для нього потрібно додаткова пам'ять розміру 2n - 1.
Страницы: 1, 2, 3, 4
|