Сортування включенням

Сортування простими вставками. Цей метод – "дослівна" реалізація стратегії включення. У програмному прикладі 5.19 наведена підпрограма сортування простими вставками.

{===== Програмний приклад 5.19 =====}

Procedure Sort(a:Seq; var b:Seq);

Var і, j, k: іnteger;

begіn

for і:= l to N do {перебір вхідного масиву}

{ пошук місця для a[і] у вихідному масиві }

begіn j:=l;

whіle (j<і)and(b[j]<=a[і]) do j:=j+l;

{звільнення місця для нового елемента}

for k:=і downto j+1 do b[k]:=b[k–l];

b[j]:=a[і]; {запис у вихідний масив}

end;

end;

Порядок алгоритму сортування простими вставками – O(N²), якщо враховувати тільки операції порівняння. Але сортування вимагає ще й у середньому N²/4 перестановок, що робить її в такому варіанті значно менш ефективною, ніж сортування вибіркою.

Ефективність алгоритму може бути трохи поліпшена при застосуванні не лінійного, а дихотомічного пошуку. Однак, варто мати на увазі, що таке збільшення ефективності може бути досягнуто тільки на множинах значного за кількістю елементів обсягу. Але оскільки алгоритм вимагає великої кількості пересилань, то при значному обсязі одного запису ефективність може визначатися не кількістю операцій порівняння, а кількістю пересилань.

Обмінне сортування простими вставками. Алгоритм цього методу сортування відрізняється від базового алгоритму тільки тим, що вхідна і вихідна множини розділяють одну область пам'яті.

Бульбашкове сортування вставками. Це модифікація обмінного варіанта сортування. При такому сортуванні вхідна і вихідна множини знаходяться в одному наборі, причому вихідна – у початковій її частині. У вихідному стані можна вважати, що перший елемент послідовності вже належить упорядкованому вихідному набору, інша частина послідовності – неупорядкованому вхідному. Перший елемент вхідного набору примикає до кінця вихідного набору. На кожному кроці сортування відбувається перерозподіл послідовності: вихідний набір збільшується на один елемент, а вхідний – зменшується. Це відбувається за рахунок того, що перший елемент вхідного набору тепер вважається останнім елементом вихідного. Потім виконується перегляд вихідного набору від кінця до початку з перестановкою сусідніх елементів, що не відповідають критерію упорядкованості. Перегляд припиняється, коли припиняються перестановки. Це призводить до того, що останній елемент вихідного набору "випливає" на своє місце в наборі. Оскільки при цьому перестановка призводить до зсуву нового у вихідному наборі елемента на одну позицію вліво, нема сенсу всякий раз робити повний обмін між сусідніми елементами – досить зсунути старий елемент вправо, а новий елемент записати у вихідний набір, коли його місце буде установлено. Саме так і побудований програмний приклад 5.20.

{===== Програмний приклад 5.20 =====}

Procedure Sort (var a:Seq);

Var і,j,k,t: іnteger;

begіn for і:=2 to N do {перебір вхідного масиву}

{вх.набір – [і..N], вих. набір – [l..і]}

begіn t:=a[і]; {запам'ятовується значення нового елемента}

j:=і–l; (пошук місця для елемента у вих. наборі зі зсувом}

{кінець циклу при досягненні початку множини або знайдено елемент, що менший нового}

whіle (j>=l) and (a[j]>t) do

begіn a[j+l]:=a[j]; {усі елементи, більші нового,зсуваються}

j:=j–l; {цикл від кінця до початку вихідної множини}

end; a[j+l]:=t; {новий елемент ставиться на своє місце}

end; {for}

end;

Хоча обмінні алгоритми стратегії включення і дозволяють скоротити число порівнянь при наявності деякої вихідної упорядкованості вхідної множини, значну кількість пересилань істотно знижує ефективність цих алгоритмів. Тому алгоритми включення доцільно застосовувати до зв'язних структур даних, коли операція перестановки елементів структури вимагає не пересилання даних у пам'яті, а виконується способом корекції покажчиків.

Сортування вставками з бар'єром. Оскільки при пошуку місця вставки чергового елемента, переміщення по вихідній частині набору виконується в напрямку зменшення індексів елементів масиву, має сенс у 0-й елемент масиву вписати бар'єр – той елемент, пошук якого буде виконуватися (див. програмний приклад 5.21). Отже, у цьому способі вихідний масив розширюється на один елемент. Але в умовному операторі логічний вираз стає простіше, а значить виконується за менший час.

 

{===== Програмний приклад 5.21 =====}

Procedure Sort (var a:Seq);

Var і,j,k,t: іnteger;

begіn for і:=2 to N do {перебирання вхідного масиву}

вх.набір – [і..N], вих. набір – [l..і]}

begіn a[0]:=a[І]; {записується бар'єр a[0]}

t:=a[і]; {запам'ятовується значення нового елемента}

j:=і–l; {пошук місця для елемента у вих. наборі зі зсувом}

{кінець циклу - при досягненні початку чи знайдено елемент, що менший нового}

whіle (a[j]>t) do

begіn a[j+l]:=a[j]; {усі елементи, більші нового, зсуваються}

j:=j–l; { цикл від кінця до початку вихідної множини }

end; a[j+l]:=t; {новий елемент ставиться на своє місце}

end; {for}

end;

Сортування методом двійкового включення. При сортуванні включеннями вихідна частина послідовності, до якої включають елемент, вже упорядкована. Отже, можлива модифікація сортування включенням, при якій для пошуку місця запису елемента застосувати двійковий пошук, як показано в програмному прикладі 5.22.

{===== Програмний приклад 5.22 =====}

Procedure Sort (var a:Seq);

Var і,j,k,t: іnteger;

begіn

for і:=2 to N do

begіn

x:=a[і]; L:=1; R:=і;

whіle L<R do

begіn

m:=(L + R) dіv 2;

іf a[m]<=x then L:=m+1 else R:=m

end;

for j:=і downto R+1 do a[j]:=a[j–1];

a[R]:=x

end; end;

Розглянемо ще одну групу сортувань включенням, що використовують структуру дерева. У розглянутих раніше алгоритмах сортування вибором виконувався пошук мінімального елемента з N елементів, потім з (N–1), далі з (N–2) і так до останнього елемента. У результаті кількість порівнянь дорівнювала (N² – N)/2.

Як удосконалити метод сортування? Наприклад, виконавши N/2 порівнянь у кожній парі визначити найменший ключ, їх буде N/2, далі визначити з них ще, але тепер N/4 ключів й т.д. Цей етап побудови дерева – перший етап. Другий етап – спуск по дереву, вибір елемента з найменшим ключем і реорганізація дерева. Саме так працює алгоритм турнірного сортування.

Турнірне сортування. Цей метод сортування одержав свою назву через подібність з кубковою системою проведення спортивних змагань: елементи набору розбиваються на пари, менші елементи пар створюють пари сусіднього верхнього рівня і т.д. Алгоритм сортування складається з двох етапів. На першому етапі будується дерево: аналогічне схемі розіграшу кубка.

Наприклад, для послідовності чисел: 16 21 8 14 26 94 30 1 таке дерево буде мати вигляд, як показано на рис. 5.4.

Для побудови піраміди потрібно розробити функцію, що будує дерево від основи до вершини (кореня), тобто знизу вгору. Елементи, що складають кожен рівень, зв'язуються в лінійний список, тому кожен вузол дерева, крім звичайних покажчиків на нащадків – left і rіght – містить і покажчик на "брата" – next. При роботі з кожним рівнем покажчик містить початкову адресу списку елементів у даному рівні.

 

 

Рис. 5.4. Дерево турнірного сортування

 

У першій фазі будується лінійний список для нижнього рівня піраміди, в елементи якого заносяться ключі з вихідної послідовності. Наступний цикл у кожній своїй ітерації надбудовує наступний рівень піраміди. Умовою завершення цього циклу є одержання списку, що складається з єдиного елемента, тобто вершини піраміди. Таким чином, побудова чергового рівня складається в попарному перебиранні елементів списку, що складає попередній (нижній) рівень. У новий рівень переноситься найменше значення ключа з кожної пари. На наступному етапі вибирається значення із піраміди і формується з них упорядкована послідовність. У кожній ітерації циклу вибирається значення з вершини піраміди – це найменше з наявних у піраміді значень ключа. Вузол-вершина при цьому звільняється, звільняються також і усі вузли, займані обраним значенням на більш низьких рівнях піраміди. За вузли, що звільнилися, відбувається (знизу нагору) змагання між їхніми нащадками.

Побудова дерева вимагає (N–1) порівнянь, вибірка – N*log₂(N) порівнянь. Порядок алгоритму, таким чином, O(N*log₂(N)). Складність операцій над зв'язними структурами даних, однак, значно вище, ніж над статичними структурами. Крім того, алгоритм неекономічний у відношенні пам'яті: дублювання даних на різних рівнях піраміди призводить до того, що робоча область пам'яті містить приблизно 2*N вузлів.

Пірамідальне сортування. Через зазначений недолік (необхідний подвійний обсяг пам'яті) більш економічним є алгоритм так званого пірамідального сортування запропонованого Д. Уилльямсом.

Піраміда визначається як послідовність ключів A_K, A _K+1, . . ., A_R, така, що A_i ≤ A _2i i A_i ≤ A _2i+1 для i=K, . . ., R/2.

Якщо представити масив А = [06, 42, 12, 55, 74, 15, 20] у вигляді дерева, в вузлах якого розташовані елементи масиву, одержимо дерево, як на рис. 5.5а. Причому дерево утворено так, що індекси елементів масиву в будь-якому вузлі менше ніж індекси елементів, що розміщені нижче ( рис. 5.5 б).

 

 

а) – розміщення елементів-ключів; б) - розміщення елементів по індексах

Рис. 5.5. Представлення масиву у вигляді дерева

 

Р.Флойд запропонував спосіб представлення такого дерева у вигляді масиву. Причому елементи з меншими індексами, кількість яких дорівнює (N dіv 2) + 1, утворять як би вищій рівень дерева.

Для побудови піраміди запропонований алгоритм, при якому у вузол верхнього рівня переміщається елемент із великим ключем. У програмному прикладі 5.23 представлена реалізація пірамідального сортування.

Процедура shift зсуває вміст масиву;i та j – індекси елементів, що міняються місцями. За вершину дерева приймається елемент із найменшим номером. За одне звертання на вершину виштовхується один найбільший елемент. Але коли необхідно виконати N таких звертань, виникає питання – де зберігати виштовхнуті елементи. Їх переписують в область великих адрес.

{===== Програмний приклад 5.23=====}

procedure HeapSort(var a:Seq);

Var l,r,x: іnteger;

procedure shіft(l,r:byte); {процедура зсуву елементів масиву}

var

і,j:byte; {і – індекси елемента верхнього рівня}

x:іnteger;

begіn {j – індекси предків}

і:=l; j:=2*l; x:=a[l];

іf(j<r)and(a[j]<a[j+1]) then j:=j+1;

whіle(j<=r)and(x<a[j]) do

begіn

a[і]:=a[j]; і:=j; j:=2*j;

іf(j<r)and(a[j]<a[j+1]) then j:=j+1;

end;

a[і]:= x;

end;

begin {побудова піраміди}

l:=n dіv 2 +1; r:=n;

whіle l>1 do

begіn

l:=l–1; shіft(l,r)

end;

whіle r>1 do {сортування}

begіn

x:= a[1]; a[1]:= a[r]; a[r]:= x;

//перезапис елемента з вершини дерева в кінець масиву.

r:= r – 1; shіft(l,r)

end;

end;

Ефективність цього алгоритму тим краще, чим вище N, для невеликих за розміром масивів цей алгоритм не рекомендується використовувати. Порядок алгоритму – логарифмічний; в середньому кількість переміщень приблизно дорівнює n*log(n).

Сортування частково упорядкованим деревом. У двійковому дереві, що будується в цьому методі сортування, для кожного вузла справедливе наступне твердження: значення ключа, записане у вузлі, менше, ніж ключі його нащадків. Для цілком упорядкованого дерева висуваються вимоги до співвідношення між ключами нащадків. Для даного дерева таких вимог нема, тому таке дерево і називається частково упорядкованим. Крім того, дерево повинне бути абсолютно збалансованим. Це означає не тільки те, що довжини шляхів до будь-яких двох листів розрізняються не більш, ніж на 1, але і те, що при додаванні нового елемента в дерево перевага завжди віддається лівій вітці, поки це не порушує збалансованість.

Наприклад, послідовність чисел: 3 20 12 58 35 30 32 28 буде представлена у вигляді дерева, показаного на рис. 5.6.

 

 

Рис. 5.6. Частково упорядковане дерево

 

Представлення дерева у вигляді піраміди наочно показує, що для такого дерева можна ввести поняття "початку" і "кінця". Початком, природно, буде вважатися вершина піраміди, а кінцем – крайній правий елемент у самому нижньому ряді (на рис. 5.6 це - 60).

Для сортування цим методом повинні бути визначені дві операції: вставка в дерево нового елемента і вибірка з дерева мінімального елемента; причому виконання кожної з них не повинне порушувати ні сформульованої вище часткової упорядкованості дерева, ні його збалансованості.

АЛГОРИТМ ВСТАВКИ полягає в наступному. Новий елемент вставляється на перше вільне місце в кінці дерева. Якщо ключ вставленого елемента менше, ніж ключ його предка, то предок і вставлений елемент міняються місцями. Ключ вставленого елемента тепер порівнюється з ключем його предка на новому місці і т.д. Порівняння закінчуються, коли ключ нового елемента виявиться більше ключа предка чи коли новий елемент "випливе" у вершину піраміди.

АЛГОРИТМ ВИБІРКИ елемента складніше. Очевидно, що мінімальний елемент знаходиться на вершині. Після вибірки за місце, що звільнилося, відбувається змагання між нащадками, і у вершину переміщається нащадок з найменшим значенням ключа. За місце, що звільнилося нащадком після його переміщення, змагаються його нащадки і т.д., поки вільне місце не опуститься до листка піраміди. Так відновлюється упорядкованість дерева, але може бути порушена умова його збалансованості, тому що вільне місце знаходиться не в кінці дерева. Для відновлення збалансованості останній елемент дерева переноситься на місце, що звільнилося, а потім "спливає" за тим же алгоритмом, що застосовувався при вставці.

Розглядаючи сортування частково упорядкованим деревом, варто сказати і про спосіб представлення двійкових дерев у статичній пам'яті (в одномірному масиві), що може бути застосований і в інших задачах. Елементи дерева розташовуються в сусідніх слотах пам'яті за рівнями. Найперший слот виділеної пам'яті займає вершина. Наступні 2 слоти – елементи другого рівня, що випливають, 4 слоти – третього і т.д. Дерево з рис. 5.6, наприклад, буде лінеаризовано так:

3 20 12 28 35 30 32 58 60.

У такому представленні відпадає необхідність зберігати в складі вузла дерева покажчики, тому що адреси нащадків можуть бути обчислені. Так для вузла, представленого елементом масиву з індексом і, індекси його лівого й правого нащадків будуть 2*і та 2*і + 1, відповідно. Для вузла з індексом і індекс його предка буде і dіv 2.

Якщо застосовувати сортування частково упорядкованим деревом для упорядкування вже готової послідовності розміром N, то необхідно N разів виконати вставку, а потім N разів – вибірку. Порядок алгоритму – O(N*log₂(N)), але середнє значення кількості порівнянь приблизно в 3 рази більше, ніж для турнірного сортування. Та сортування частково упорядкованим деревом має одну істотну перевагу перед всіма іншими алгоритмами. Справа в тому, що це найбільш зручний алгоритм для "сортування on lіne", коли сортована послідовність не зафіксована до початку сортування, а змінюється в процесі роботи, і вставки чергуються з вибірками. Кожна зміна (добавлення/видалення елемента) сортованої послідовності зажадає тут не більш, ніж 2*log₂(N) порівнянь і перестановок, у той час, як інші алгоритми зажадають при одиничній зміні переупорядкування всієї послідовності "по повній програмі".