Алгоритми пошуку
Лінійний пошук
Якщо нема додаткових вказівок про розташування необхідного елемента, то природнім є послідовний перегляд масиву із збільшенням тієї його частини, де бажаного елементу не знайдено. Такий метод називається лінійним пошуком. Умови закінчення пошуку тнаступні.
Елемент знайдений, тобто аi = x.
Весь масив проглянутий і збігу не знайдено.
Це дає нам лінійний алгоритм:
Слід звернути увагу, що якщо елемент знайдений, то він знайдений разом з мінімально можливим індексом, тобто це перший з таких елементів. Очевидно, що закінчення циклу гарантоване, оскільки на кожному кроці значення i збільшується, і, отже, воно досягне за скінченну кількість кроків межі N; фактично ж, якщо збігу не було, це відбудеться після N кроків.
Двійковий (бінарний) пошук елементу в масиві
Якщо у нас є масив, що містить впорядковану послідовність даних, то дуже ефективний двійковий пошук.
Змінні Lb і Ub містять, відповідно, ліву і праву межі відрізка масиву, де знаходиться потрібний елемент. Починаємо завжди з дослідження середнього елементу відрізка. Якщо шукане значення менше середнього елементу, ми переходимо до пошуку у верхній половині відрізка, де всі елементи менші від тільки що перевіреного. Іншими словами, значенням Ub стає (M – 1) і на наступній ітерації ми працюємо з половиною масиву. Таким чином, в результаті кожної перевірки ми удвічі звужуємо область пошуку.
Інтерполяційний пошук елементу в масиві
Якщо відомо, що До лежить між Kl і Ku, то наступний пошук доцільно робити не всередині впорядкованого масиву, а на відстані (u-l)(K-Kl)/(Ku-Kl) від l, припускаючи, що ключі є числами, що зростають приблизно в арифметичній прогресії.
Інтерполяційний пошук працює за log log N операцій, якщо дані розподілені рівномірно. Як правило, він використовується лише на дуже великих таблицях, причому робиться декілька кроків інтерполяційного пошуку, а потім на малому підмасиві використовується бінарний або послідовний варіанти.
Бінарний пошук з визначенням найближчих вузлів
У ряді випадків (зокрема, в завданнях інтерполяції) доводиться з'ясовувати, де по відношенню до заданого впорядкованого масиву дійсних чисел розташовується задане дійсне число. На відміну від пошуку в масиві цілих чисел, задане число в цьому випадку найчастіше не співпадає ні з одним з чисел масиву, і вимагається знайти номери елементів, між якими це число може бути розміщене.
Один з найшвидших способів цього є бінарний пошук, характерна кількість операцій якого має порядок log2(n), де n – кількість елементів масиву. При численних зверненнях до цієї процедури кількість операцій буде рівна m log2(n) (m – кількість обходів). Прискорення цієї процедури можна добитися за рахунок збереження попереднього результату операції і спроб пошуку при новому обігу в найближчих вузлах масиву з подальшим розширенням області пошуку у разі неуспіху.
При цьому в якнайгірших випадках кількість операцій буде більшою (приблизно у 2 рази) в порівнянні з бінарним пошуком, але, зазвичай, при m, значно більшою, ніж log2(n), вдається довести порядок кількості операцій до m, тобто зробити її майже незалежною від розміру масиву.
Завдання ставиться так. Заданий впорядкований масив дійсних чисел array розмірності n, значення value, що перевіряється, і початкове наближення вузла old. Вимагається знайти номер вузла res масиву array, такий, що array[res]<=value<array[res+1]
Алгоритм працює таким чином.
1. Визначається, чи лежить значення value за межами масиву array. У разі value<array[0] повертається -1, у разі value>array[n-1] повертається n-1.
2. Інакше перевіряється: якщо значення old лежить за межами індексів масиву (тобто old<0 або old>=n, то переходимо до звичного бінарного пошуку, встановивши ліву межу left=0, праву right=n-1.
3. Інакше переходимо до з'ясування меж пошуку. Встановлюється left=right=old, inc=1 -- інкремент пошуку.
4. Перевіряється нерівність value>=array[old]. При його виконанні переходимо до наступного пункту (5), інакше до пункту (7).
5. Права межа пошуку відводиться далі: right=right+inc. Якщо right>=n-1, то встановлюється right=n-1 і переходимо до бінарного пошуку.
6. Перевіряється value>=array[right]. Якщо ця нерівність виконується, то ліва межа переміщається на місце правої: left=right, inc умножається на 2, і переходимо назад на (5). Інакше переходимо до бінарного пошуку.
7. Ліва межа відводиться: left=left-inc. Якщо left<=0, то встановлюємо left=0 і переходимо до бінарного пошуку.
8. Перевіряється value<array[left]. При виконанні права межа переміщається на місце лівої: right=left, inc умножається на 2, переходимо до пункту (7). Інакше до бінарного пошуку.
9. Проводиться бінарний пошук в масиві з обмеженням індексів left і right. При цьому кожного разу інтервал скорочується приблизно в 2 рази (у зачисимості від парності різниці), поки різниця між left і right не досягне 1. Після цього повертаємо left як результат, одночасно привласнюючи old=left.
Пошук в таблиці
Пошук в масиві іноді називають пошуком в таблиці, особливо якщо ключ сам є складовим об'єктом, таким, як масив чисел або символів. Часто зустрічається саме останній випадок, коли масиви символів називають рядками або словами. Рядковий тип визначається так:
String = array[0..Мv1] of char
відповідно визначається і відношення порядку для рядків x і у:
x = у, якщо xj = yj для 0 face="Symbol" =< j < M
x < у, якщо xi < yi для 0 face="Symbol" =< i < M і xj = yj для 0 face="Symbol" =< j < i
Для того, щоб встановити факт збігу, необхідно встановити, що всі символи порівнюваних рядків відповідно рівні один іншому. Тому порівняння складових операндів зводиться до пошуку їх неспівпадаючих частин, тобто до пошуку на нерівність. Якщо нерівних частин не існує, то можна говорити про рівність. Припустимо, що розмір слів достатньо малий, скажімо, менше 30. В цьому випадку можна використовувати лінійний пошук і поступати таким чином.
Для більшості практичних додатків бажано виходити з того, що рядки мають змінний розмір. Це припускає, що розмір указується в кожному окремому рядку. Якщо виходити з раніше описаного типу, то розмір не повинен перевершувати максимального розміру M. Така схема достатньо гнучка і підходить для багатьох випадків, в той же час вона дозволяє уникнути складнощів динамічного розподілу пам'яті. Найчастіше використовуються два такі подання розміру рядків.
Розмір неявно вказується шляхом додавання кінцевого символу, більше цей символ ніде не уживається. Зазвичай, для цієї мети використовується недрукований символ із значенням 00h. (Для подальшого важливо, що це мінімальний символ зі всієї множини символів.)
Розмір явно зберігається як перший елемент масиву, тобто рядок s має наступний вигляд: s = s0, s1, s2, ..., sM-1. Тут s1, ..., sM-1 v фактичні символи рядка, а s0 = Chr(M). Такий прийом має ту перевагу, що розмір явно доступний, недолік же у тому, що цей розмір обмежений розміром множини символів (256).
У подальшому алгоритмі пошуку віддається перевага першій схемі. У цьому випадку порівняння рядків виконується так:
i:=0;
while (x[i]=y[i]) and (x[i]<>00h) do i:=i+1;
Кінцевий символ працює тут як бар'єр.
Тепер повернемося до завдання пошуку в таблиці. Він вимагає вкладених пошуків, а саме: пошуку по стрічкам таблиці, а для кожної строчки послідовних порівнянь v між компонентами. Наприклад, нехай таблиця T і аргумент пошуку x визначаються таким чином:
T: array[0..N-1] of String;
x: String;
Прямий пошук рядка
Часто доводиться зустрічатись зі специфічним пошуком, так званим пошуком рядка. Його можна визначити таким чином. Нехай заданий масив s з N елементів і масив p з M елементів, причому 0 < M face="Symbol" =< N. Описані вони так:
s: array[0..Nv1] of Item
р: array[0..Mv1] of Item
Пошук рядка знаходить перше входження p в s. Зазвичай, Item v – це символи, тобто s можна вважати деяким текстом, а p v словом, і необхідно знайти перше входження цього слова у вказаному тексті. Ця дія типова для будь-яких систем опрацювання текстів, звідси і очевидна зацікавленість в пошуку ефективного алгоритму для цього завдання. Розглянемо алгоритм пошуку, який називатимемо прямим пошуком рядка.
i:=-1;
repeat
i:=i+1; j:=0;
while (j<M) and (s[i+j]=p[j]) do j:=j+1;
until (j=M) or (i=N-M)
Вкладений цикл з передумовою починає виконуватися тоді, коли перший символ слова p співпадає з черговим, i-м, символом тексту s. Цей цикл повторюється стільки разів, скільки співпадає символів тексту s, починаючи з i-го символу, з символами слова p (максимальна кількість повторень рівна M). Цикл завершується при вичерпанні символів слова p (перестає виконуватися умова j<M) або при неспівпаданні чергових символів s і p (перестає виконуватися умова s[i+j]=p[j]). Кількість співпадінь підраховується з використанням j. Якщо співпадіння відбулося зі всіма символами слова p (тобто слово p знайдене), то виконується умова j=M, і алгоритм завершується. Інакше пошук продовжується до тих пір, поки не переглянутою залишиться частина тексту s, яка містить символів менше, ніж є в слові p (тобто цей залишок вже не може співпасти із словом p). В цьому випадку виконується умова i=N-M, що теж приводить до завершення алгоритму. Це показує гарантованість закінчення алгоритму.
Цей алгоритм працює достатньо ефективно, якщо припустити, що неспівпадання пари символів відбувається після незначної кількості порівнянь у внутрішньому циклі. При великій потужності типу Item це достатньо частий випадок. Можна припускати, що для текстів, складених з 128 символів, неспівпадання виявлятиметься після одної або двох перевірок. Проте, у гіршому разі продуктивність може виявитися набагато гіршою.
Алгоритм Кнута, Моріса і Пратта
Приблизно в 1970 р. Д. Кнут, Д. Моріс і В. Пратт винайшли алгоритм (КМП), що фактично вимагає тільки N порівнянь навіть в найгіршому випадку. Новий алгоритм ґрунтується на тому міркуванні, що після часткового співпадіння початкової частини слова з відповідними символами тексту фактично відома пройдена частина тексту і можна визначити деякі відомості (на основі самого слова), за допомогою яких потім можна швидко просунутися по тексту. Приведений приклад пошуку слова ABCABD показує принцип роботи такого алгоритму. Символи, що порівнювалися, тут підкреслені. Зверніть увагу: при кожному неспівпаданні пари символів слово зсувається на усю пройдену відстань, оскільки менші зсуви не можуть привести до повного співпадіння.

Основною відмінністю КМП-алгоритму від алгоритму прямого пошуку є здійснення зсуву слова не на один символ на кожному кроці алгоритму, а на деяку змінну кількість символів. Таким чином, перш ніж здійснювати черговий зсуву, необхідно визначити величину зсуву. Для підвищення ефективності алгоритму необхідно, щоб зсуву на кожному кроці був якомога більшим.
Якщо j визначає позицію в слові, що містить перший неспівпадаючий символ (як в алгоритмі прямого пошуку), то величина зсуву визначається як j-D. Значення D визначається як розмір найдовшої послідовності символів слова, які безпосередньо передують позиції j, і яка повністю співпадає з початком слова. D залежить тільки від слова і не залежить від тексту. Для кожного j буде своя величина D, яку позначимо dj.
Оскільки величини dj залежать тільки від слова, то перед початком фактичного пошуку можна обчислити допоміжну таблицю d; ці обчислення зводяться до деякої передтрансляції слова. Відповідні зусилля будуть виправданими, якщо розмір тексту значно перевищує розмір слова (M<<N). Якщо потрібно шукати багато входжень одного і того ж слова, то можна користуватися одними і тими ж d. Точний аналіз КМП-пошуку, як і сам його алгоритм, вельми складний. Його винахідники доводять, що потрібно порядку M+N порівнянь символів, що значно краще, ніж M*N порівнянь з прямого пошуку. Вони так само відзначають таку позитивну властивість, як показник сканування, який ніколи не повертається назад, тоді як при прямому пошуку після неспівпадання перегляд завжди починається з першого символу слова і тому може включати символи, які раніше вже були видимими. Це може привести до негативних наслідків, якщо текст читається з вторинної пам'яті, адже в цьому випадку повернення обходиться дорого. Навіть при введенні, що буферизує, може зустрітися таке велике слово, що повернення перевищить місткість буфера.
Алгоритм Боуєра і Мура
КМП-пошук дає справжній виграш тільки тоді, коли невдачі передувала деяка кількість співпадінь. Лише в цьому випадку слово зсувається більше ніж на одиницю. На нещастя, це швидше виключення, ніж правило: співпадіння зустрічаються значно рідше, ніж неспівпадіння. Тому виграш від використання КМП-стратегії в більшості випадків пошуку в звичних текстах вельми незначний. Метод, запропонований Р. Боуером і Д. Муром в 1975 р., не тільки покращує обробку найгіршого випадку, але дає виграш в проміжних ситуаціях.
БМ-пошук ґрунтується на незвичайному міркуванні v порівняння символів починається з кінця слова, а не з початку. Як і у випадку КМП-пошуку, слово перед фактичним пошуком трансформується в деяку таблицю. Нехай для кожного символу x з алфавіту величина dx v відстань від найправішого в слові входження x до правого кінця слова. Уявимо собі, що знайдено розбіжність між словом і текстом. В цьому випадку слово відразу ж можна зсунути вправо на dpM-1 позицій, тобто на кількість позицій, швидше за все більшу за одиницю. Якщо неспівпадаючий символ тексту в слові взагалі не зустрічається, то зсув стає навіть більшим, а саме зсувати можна на довжину всього слова.
Майже завжди, окрім спеціально побудованих прикладів, поданий алгоритм вимагає значно менше N порівнянь. За найсприятливіших обставин, коли останній символ слова завжди потрапляє на неспівпадаючий символ тексту, кількість порівнянь буде рівна N/M.
Контрольні запитання
Наведіть приклади використання алгоритмів пошуку.
Поясність особливості алгоритмів пошуку стрічок.
Порівняйте алгоритми лінійного та бінарного пошуку.
Навіть алгоритми пошуку стрічок.
Тести для закріплення матеріалу
1. Перерахувати алгоритми пошуку
бульбашки,
лінійний,
ортогональний,
бінарний,
інтерполяційний.
2. Перерахувати алгоритми пошуку
бульбашки,
лінійний,
Боуєра і Мура,
бінарний,
Батога, Моріса і Пратта.
3. Перерахувати алгоритми пошуку в стрічках
Боуєра і Мура,
бінарний,
Батога, Моріса і Пратта,
прямий пошук,
паралельний пошук.
Алгоритми сортування
Сортування застосовується в усіх без винятку областях програмування, будь те бази даних чи математичні програми.
Практично кожен алгоритм сортування можна розбити на три частини:
порівняння, що визначає упорядкованість парі елементів;
перестановку, що змінює місцями пари елементів;
власне алгоритм сортування, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть упорядковані.
Методи внутрішнього сортування
У загальній постановці завдання сортування ставиться таким чином. Є послідовність однотипних записів, одне з полів яких вибране як ключовий (далі ми називатимемо його ключем сортування). Тип даних ключа повинен включати операції порівняння ("=", ">", "<", ">=" і "<="). Завданням сортування є перетворення початкової послідовності в послідовність, що містить ті ж записи, але у порядку зростання (або убування) значень ключа. Метод сортування називається стійким, якщо при його застосуванні не змінюється відносне положення записів з рівними значеннями ключа.
Розрізняють сортування масивів записів, розташованих в основній пам'яті (внутрішнє сортування), і сортування файлів, що зберігаються в зовнішній пам'яті і не поміщаються повністю в основній пам'яті (зовнішнє сортування). Для внутрішнього і зовнішнього сортування потрібні істотно різні методи.
Природною умовою, що висувається до будь-якого методу внутрішнього сортування є те, що ці методи не повинні вимагати додаткової пам'яті: всі перестановки з метою впорядкування елементів масиву повинні вироблятися в межах того ж масиву. Мірою ефективності алгоритму внутрішнього сортування є кількість необхідних порівнянь значень ключа (C) і кількість перестановок елементів (M).
Помітимо, що оскільки сортування засноване тільки на значеннях ключа і ніяк не зачіпає поля записів, що залишилися, можна говорити про сортування масивів ключів.
Сортування включенням
Метод простого включення
Нехай є масив ключів а[1], а[2], ..., а[n]. Для кожного елементу масиву, починаючи з другого, здійснюється порівняння з елементами з меншим індексом (елемент а[i] послідовно порівнюється з елементами а[i-1], а[i-2] ...) і до тих пір, поки для чергового елементу а[j] виконується співвідношення а[j]> а[i], а[i] і а[j] міняються місцями. Якщо вдається зустріти такий елемент а[j], що а[j]<= а[i], або якщо досягнута нижня межа масиву, здійснюється перехід до опрацювання елементу а[i+1] (поки не буде досягнута верхня межа масиву) (рис. 6.1).
Легко бачити, що в кращому разі (коли масив вже впорядкований) для виконання алгоритму з масивом з n елементів буде потрібно n-1 порівняння і 0 пересилань. У гіршому разі (коли масив впорядкований в зворотному порядку) буде потрібно n*(n-1)/2 порівнянь і стільки ж пересилань. Таким чином, можна оцінювати складність методу простих включень як Про(n2).

Рис. 6.1. Блок-схема сортування методом включення
Можна скоротити кількість порівнянь, що використовуються в методі простих включень, якщо скористатися тим фактом, що при опрацюванні елементу масиву а[i] елементи а[1], а[2], ..., а[i-1] вже впорядковані, і скористатися для пошуку елементу, з яким повинна бути здійснена перестановка, методом двійкового розподілу. В цьому випадку оцінка кількості необхідних порівнянь стає Про(nlog n). Помітимо, що оскільки при виконанні перестановки потрібне зсування на один елемент декількох елементів, то оцінка кількості пересилань залишається Про(n2).
Таблиця 1 Приклад сортування методом простого включення
Початковий стан масиву
8 23 5 65 44 33 1 6

Крок 1
8 23 5 65 44 33 1 6

Крок 2
8 5 23 65 44 33 1 6


5 8 23 65 44 33 1 6

Крок 3
5 8 23 65 44 33 1 6

Крок 4
5 8 23 44 65 33 1 6

Крок 5
5 8 23 44 33 65 1 6


5 8 23 33 44 65 1 6

Крок 6
5 8 23 33 44 1 65 6


5 8 23 33 1 44 65 6


5 8 23 1 33 44 65 6


5 8 1 23 33 44 65 6


5 1 8 23 33 44 65 6


1 5 8 23 33 44 65 6

Крок 7
1 5 8 23 33 44 6 65


1 5 8 23 33 6 44 65


1 5 8 23 6 33 44 65


1 5 8 6 23 33 44 65


1 5 6 8 23 33 44 65

Метод Шелла
Подальшим розвитком методу сортування з включеннями є сортування методом Шелла, яке по-іншому називається сортуванням включеннями з відстанню, що зменшується.
Метод полягає в тому, що таблиця, яка впорядковується, розділяється на групи елементів, кожна з який упорядковується методом простих включень. У процесі впорядкування розміри таких груп збільшуються доти, поки всі елементи таблиці не ввійдуть у впорядковану групу. Вибір чергової групи для сортування і її розташування усередині таблиці здійснюється так, щоб можна було використовувати попередню упорядкованість. Групою таблиці називають послідовність елементів, номера яких утворять арифметичну прогресію з різницею h (h називають кроком групи). На початку процесу упорядкування вибирається перший крок групи h1, що залежить від розміру таблиці. Шелл запропонував брати
h1=[n/2], а hi=h((і-1)/2).
У більш пізніх роботах Хіббард показав, що для прискорення процесу доцільно визначити крок h1 за формулою:
h1=2**k+1 , де 2**k < n <= 2**(k+1).
Після вибору h1 методом простих включень впорядковуються групи, що містять елементи з номерами позицій і, і+h1, і+2*h1, ..., і+mi*h1.
При цьому і=1,2,...,h1; m[і] – найбільше ціле, що задовольняє нерівності і+m[і]*hi <= n.
Потім вибирається крок h2<h1 і впорядковуються групи, що містять елементи з номерами позицій і, і+h2, ..., і+m[і]*h2. Ця процедура з усе зменшуваними кроками продовжується доти, поки черговий крок h[l] стане рівним одиниці (h1>h2>...>hl). Цей останній етап являє собою впорядкування всієї таблиці методом включень. Але оскільки вихідна таблиця впорядковувалася окремими групами з послідовним об'єднанням цих груп, то загальна кількість порівнянь значно менша, ніж n /4, необхідна при методі включень. Кількість операцій порівняння пропорційна n*(log2(n))**2 .
Застосування методу Шелла до масиву, використаного в наших прикладах, показано в таблиці 2.
У загальному випадку алгоритм Шелла природно переформулюється для заданої послідовності з t відстаней між елементами h1, h2, ..., ht, для яких виконуються умови h1 = 1 і h(i+1)< hi. При правильно підібраних t і h складність алгоритму Шелла є Про(n(1.2)), що істотно менша за складність простих алгоритмів сортування.
Блок-схема методу Шелла подана на рис. 6.2. У ньому використано змінні:
а[] – массив, який необхідно відсортувати,
t – допоміжна змінна того ж типу, що і масив,
n – розмірність масиву.

Рис. 6.2 Блок-схема методу Шелла.
Таблиця 2. Приклад сортування методом Шелла
Початковий стан масиву
8 23 5 65 44 33 1 6

Фаза 1 (сортуються елементи, відстань між якими чотири)
8 23 5 65 44 33 1 6


8 23 5 65 44 33 1 6


8 23 1 65 44 33 5 6


8 23 1 6 44 33 5 65

Фаза 2 (сортуються елементи, відстань між якими два)
1 23 8 6 44 33 5 65


1 23 8 6 44 33 5 65


1 23 8 6 5 33 44 65


1 23 5 6 8 33 44 65


1 6 5 23 8 33 44 65


1 6 5 23 8 33 44 65


1 6 5 23 8 33 44 65

Фаза 3 (сортуються елементи, відстань між якими один)
1 6 5 23 8 33 44 65


1 5 6 23 8 33 44 65


1 5 6 23 8 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


Обмінне сортування
Просте обмінне сортування («методом бульбашки») для масиву а[1], а[2], ..., а[n] працює таким чином. Починаючи з кінця масиву порівнюються два сусідні елементи (а[n] і а[n-1]). Якщо виконується умова а[n-1]> а[n], то значення елементів міняються місцями. Процес продовжується для а[n-1] і а[n-2] і т.д., поки не буде вироблено порівняння а[2] і а[1]. Зрозуміло, що після цього на місці а[1] виявиться елемент масиву з якнайменшим значенням. На другому кроці процес повторюється, але останніми порівнюються а[3] і а[2]. І так далі. На останньому кроці порівнюватимуться тільки поточні значення а[n] і а[n-1]. Зрозуміла аналогія з бульбашкою, оскільки найменші елементи («найлегші») поступово «спливають» до верхньої межі масиву. Приклад сортування методом бульбашки показаний в таблиці 3.
Для методу простого обмінного сортування потрібна кількість порівнянь nx(n-1) /2, мінімальна кількість пересилань 0, а середня і максимальна кількість пересилань – Про(n2).
Метод бульбашки допускає три прості удосконалення. По-перше, як показує таблиця 3, на чотири останніх кроках розташування значень елементів не мінялося (масив виявився вже впорядкованим). Тому, якщо на деякому кроці не було вироблено жодного обміну, то виконання алгоритму можна припиняти. По-друге, можна запам'ятовувати якнайменше значення індексу масиву, для якого на поточному кроці виконувалися перестановки.
Таблиця 3. Приклад сортування методом бульбашки
Початковий стан масиву
8 23 5 65 44 33 1 6

Крок 1
8 23 5 65 44 33 1 6


8 23 5 65 44 1 33 6


8 23 5 65 1 44 33 6


8 23 5 1 65 44 33 6


8 23 1 5 65 44 33 6


8 1 23 5 65 44 33 6


1 8 23 5 65 44 33 6

Крок 2
1 8 23 5 65 44 6 33


1 8 23 5 65 6 44 33


1 8 23 5 6 65 44 33


1 8 23 5 6 65 44 33


1 8 5 23 6 65 44 33


1 5 8 23 6 65 44 33

Крок 3
1 5 8 23 6 65 33 44


1 5 8 23 6 33 65 44


1 5 8 23 6 33 65 44


1 5 8 6 23 33 65 44


1 5 6 8 23 33 65 44

Крок 4
1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65

Крок 5
1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65

Крок 6
1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65

Крок 7
1 5 6 8 23 33 44 65


Очевидно, що верхня частина масиву до елементу з цим індексом вже відсортована, і на наступному кроці можна припиняти порівняння значень сусідніх елементів досягши такого значення індексу. По-третє, метод бульбашки працює нерівноправно для «легких» і «важких» значень. Легке значення потрапляє на потрібне місце за один крок, а важке на кожному кроці опускається у напрямку до потрібного місця на одну позицію.

Рис. 6.3. Алгоритм сортування методом бульбашки.
На цих спостереженнях заснований метод шейкерного сортування (ShakerSort). При його застосуванні на кожному наступному кроці змінюється напрям послідовного перегляду. В результаті на одному кроці «спливає» черговий найлегший елемент, а на іншому «тоне» черговий найважчий. Приклад шейкерного сортування приведений в таблиці 4.
Шейкерне сортування дозволяє скоротити кількість порівнянь (за оцінкою Батога середньою кількістю порівнянь є (n2 - n?(const + ln n)), хоча порядком оцінки як і раніше залишається n2. Кількість ж пересилок, взагалі кажучи, не змінюється. Шейкерне сортування рекомендується використовувати в тих випадках, коли відомо, що масив «майже впорядкований».
Таблиця 4. Приклад шейкерного сортування
Початковий стан масиву
8 23 5 65 44 33 1 6

Крок 1
8 23 5 65 44 33 1 6


8 23 5 65 44 1 33 6


8 23 5 65 1 44 33 6


8 23 5 1 65 44 33 6


8 23 1 5 65 44 33 6


8 1 23 5 65 44 33 6


1 8 23 5 65 44 33 6

Крок 2
1 8 23 5 65 44 33 6


1 8 5 23 65 44 33 6


1 8 5 23 65 44 33 6


1 8 5 23 44 65 33 6


1 8 5 23 44 33 65 6


1 8 5 23 44 33 6 65

Крок 3
1 8 5 23 44 6 33 65


1 8 5 23 6 44 33 65


1 8 5 6 23 44 33 65


1 8 5 6 23 44 33 65


1 5 8 6 23 44 33 65

Крок 4
1 5 6 8 23 44 33 65


1 5 6 8 23 44 33 65


1 5 6 8 23 44 33 65


1 5 6 8 23 33 44 65

Крок 5
1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65


1 5 6 8 23 33 44 65

Сортування вибором
При сортуванні масиву а[1], а[2], ..., а[n] методом простого вибору серед всіх елементів знаходиться елемент з якнайменшим значенням а[i], і а[1] і а[i] обмінюються значеннями. Потім цей процес повторюється для одержуваних підмасивів а[2], а[3], ..., а[n] ... а[j], а[j+1], ..., а[n] до тих пір, поки ми не дійдемо до підмасиву а[n], що містить до цього моменту найбільше значення. Робота алгоритму ілюструється прикладом в таблиці 5.
Для методу сортування простим вибором необхідна кількість порівнянь – nx(n-1) /2. Порядок необхідної кількості пересилок (включаючи ті, які потрібні для вибору мінімального елементу) у гіршому разі складає Про(n2). Проте порядок середньої кількості пересилань є Про(n?ln n), що у ряді випадків робить цей метод одним із найкращих.
Таблиця.5. Приклад сортування простим вибором
Початковий стан масиву
8 23 5 65 44 33 1 6

Крок 1
1 23 5 65 44 33 8 6

Крок 2
1 5 23 65 44 33 8 6

Крок 3
1 5 6 65 44 33 8 23

Крок 4
1 5 6 8 44 33 65 23

Крок 5
1 5 6 8 33 44 65 23

Крок 6
1 5 6 8 23 44 65 33

Крок 7
1 5 6 8 23 33 65 44

Крок 8
1 5 6 8 23 33 44 65


Сортування поділом (Quicksort)
Метод сортування поділом був запропонований Чарльзом Хоаром в 1962 р. Цей метод є розвитком методу простого обміну і настільки ефективний, що його стали називати «методом швидкого сортування – Quicksort».
Основна ідея алгоритму полягає у тому, що випадковим чином вибирається деякий елемент масиву x, після чого масив є видимим зліва, поки не зустрінеться елемент а[i] такий, що а[i]> x, а потім масив є видимим справа, поки не зустрінеться елемент а[j] такий, що а[j]< x. Ці два елементи міняються місцями, і процес перегляду, порівняння і обміну продовжується, поки ми не дійдемо до елементу x. В результаті масив виявиться розбитим на дві частини - ліву, в якій значення ключів будуть менші x, і праву із значеннями ключів, великими x. Далі процес рекурсивно продовжується для лівої і правої частин масиву до тих пір, поки кожна частина не міститиме в точності один елемент. Зрозуміло, що як завжди, рекурсію можна замінити ітераціями, якщо запам'ятовувати відповідні індекси масиву. Прослідкуємо цей процес на прикладі нашого стандартного масиву (таблиця 6).
Таблиця 6. Приклад швидкого сортування
Початковий стан масиву
8 23 5 65 |44| 33 1 6

Крок 1 (як x вибирається а[5])
8 23 5 6 44 33 1 65


8 23 5 6 1 33 44 65

Крок 2 (у підмасиві а[1], а[5] як x вибирається а[3])
8 23 |5| 6 1 33 44 65


1 23 5 6 8 33 44 65


1 5 23 6 8 33 44 65

Крок 3 (у підмасиві а[3], а[5] як x вибирається а[4])
1 5 23 |6| 8 33 44 65


1 5 8 6 23 33 44 65

Крок 4 (у підмасиві а[3], а[4] вибирається а[4])
1 5 8 |6| 23 33 44 65


1 5 6 8 23 33 44 65

Алгоритм недаремно називається швидким сортуванням, оскільки для нього оцінкою кількості порівнянь і обмінів є Про(n*?log n). Насправді, в більшості утиліт, що виконують сортування масивів, використовується саме цей алгоритм.
Сортування за допомогою дерева (Heapsort)
Почнемо з простого методу сортування за допомогою дерева, при використанні якого явно будується двійкове дерево порівняння ключів. Побудова дерева починається з листя, яке містить всі елементи масиву. З кожної сусідньої пари вибирається найменший елемент, і ці елементи утворюють наступний (ближче до кореня рівень дерева). З кожної сусідньої пари вибирається найменший елемент і т.д., поки не буде побудований корінь, тобто найменший елемент масиву. Приклад двійкового дерева показано на рис. 6.4. Отже, ми вже маємо якнайменше значення елементів масиву. Для того, щоб одержати наступний по величині елемент, спустимося від коріння по шляху, ведучому до листа з якнайменшим значенням. У цій листовій вершині проставляється фіктивний ключ з "нескінченно великим" значенням, а у все проміжні вузли, що займалися якнайменшим елементом, заноситься якнайменше значення з вузлів - безпосередніх нащадків (рис. 6.5). Процес продовжується до тих пір, поки всі вузли дерева не будуть заповнені фіктивними ключами (рисунки 6.7 – 6.11).

Рис. 6.4. Перший крок.

Рис. 6.5. Другий крок.

Рис. 6.6. Третій крок.

Рис. 6.7. Четвертий крок.

Рис. 6.8. П'ятий крок.

Рис. 6.9. Шостий крок.

Рис. 6.10. Сьомий крок.

Рис. 6.11. Восьмий крок.
На кожному з n кроків, що вимагаються для сортування масиву, потрібно провести log n (двійковий) порівнянь. Отже, всього буде потрібно n*log n порівнянь, але для подання дерева знадобиться 2n - 1 додаткова одиниця пам'яті.
Пірамідальне сортування
Є досконаліший алгоритм, який прийнято називати пірамідальним сортуванням (Heapsort). Його ідея полягає у тому, що замість повного дерева порівняння початковий масив а[1], а[2], ..., а[n] перетвориться в піраміду, що володіє тією властивістю, що для кожного а[i] виконуються умови а[i]<= а[2i] і а[i]<= а[2i+1]. Потім піраміда використовується для сортування.
Найнаочніше метод побудови піраміди виглядає при деревовидному представленні масиву показаному на рис. 6.12. Масив подається у вигляді двійкового дерева, корінь якого відповідає елементу масиву а[1]. На другому ярусі знаходяться елементи а[2] і а[3]. На третьому – а[4], а[5], а[6], а[7] і т.д. Як видно, для масиву з непарною кількістю елементів відповідне дерево буде збалансованим, а для масиву з парною кількістю елементів n елемент а[n] буде єдиним (найлівішим) листом «майже» збалансованого дерева.

Рис. 6.12. Приклад пірамідального сортування.
Очевидно, що при побудові піраміди нас цікавитимуть елементи а[n/2], а[n/2-1], ..., а[1] для масивів з парною кількістю елементів і елементи а[(n-1)/2], а[(n-1)/2-1], ..., а[1] для масивів з непарною кількістю елементів (оскільки тільки для таких елементів істотні обмеження піраміди). Нехай i – найбільший індекс з індексів елементів, для яких існують обмеження піраміди. Тоді береться елемент а[i] в побудованому дереві і для нього виконується процедура просівання, що полягає у тому, що вибирається гілка дерева, яка відповідає min(а[2i], а[2i+1]), і значення а[i] міняється місцями із значенням відповідного елементу. Якщо цей елемент не є листом дерева, для нього виконується аналогічна процедура і т.д. Такі дії виконуються послідовно для а[i], а[i-1], ..., а[1]. Легко бачити, що в результаті ми одержимо деревовидне подання піраміди для початкового масиву (послідовність кроків для використовуваного в наших прикладах масиву показана на рис. 6.13 – 16).

Рис. 6.13. Пірамідальне сортування. Крок 1.

Рис. 6.14. Пірамідальне сортування. Крок 2.

Рис. 6.15. Пірамідальне сортування. Крок 3.

Рис. 6.16. Пірамідальне сортування. Крок 4.

Рис. 6.17 Блок-схема методу впорядкування піраміди.

Рис. 6.18. Блок-схема побудови піраміди та її перевірки.

Побудова піраміди методом Флойда
У 1964 р. Флойд запропонував метод побудови піраміди без явної побудови дерева (хоча метод заснований на тих же ідеях). Побудова піраміди методом Флойда для нашого стандартного масиву показана в таблиці 7.
Таблиця 7 Приклад побудови піраміди
Початковий стан масиву
8 23 5 |65| 44 33 1 6

Крок 1
8 23 |5| 6 44 33 1 65

Крок 2
8 |23| 1 6 44 33 5 65

Крок 3
|8| 6 1 23 44 33 5 65

Крок 4

1 6 8 23 44 33 5 65


1 6 5 23 44 33 8 65

У таблиці 8 показано, як здійснюється сортування з використанням побудованої піраміди. Суть алгоритму полягає в наступному. Нехай i – найбільший індекс масиву, для якого вказані умови піраміди. Тоді, починаючи з а[1] до а[i], виконуються наступні дії. На кожному кроці вибирається останній елемент піраміди (у нашому випадку першим буде вибраний елемент а[8]). Його значення міняється зі значенням а[1], після чого для а[1] виконується просівання. При цьому на кожному кроці кількість елементів в піраміді зменшується на 1 (після першого кроку як елементи піраміди розглядаються а[1], а[2], ..., а[n-1]; після другого – а[1], а[2], ..., а[n-2] і т.д., поки в піраміді не залишиться один елемент). Легко бачити (це ілюструється в таблиці 8), що в результаті ми одержимо масив, впорядкований у порядку спадання. Можна модифікувати метод побудови піраміди і сортування, щоб одержати впорядкування у порядку зростання, якщо змінити умову піраміди а[i]>= а[2i] і а[1]>= а[2i+1] для всіх значень індексу i.
Таблиця 8 Сортування за допомогою піраміди
Початкова піраміда
1 6 5 23 44 33 8 65

Крок 1
65 6 5 23 44 33 8 1


5 6 65 23 44 33 8 1


5 6 8 23 44 33 65 1

Крок 2
65 6 8 23 44 33 5 1


6 65 8 23 44 33 5 1


6 23 8 65 44 33 5 1

Крок 3
33 23 8 65 44 6 5 1


8 23 33 65 44 6 5 1

Крок 4
44 23 33 65 8 6 5 1


23 44 33 65 8 6 5 1

Крок 5
65 44 33 23 8 6 5 1


33 44 65 23 8 6 5 1

Крок 6
65 44 33 23 8 6 5 1


44 65 33 23 8 6 5 1

Крок 7
65 44 33 23 8 6 5 1


Процедура сортування з використанням піраміди вимагає виконання порядку nxlog n кроків (логарифм – двійковий) у гіршому разі, що робить її особливо привабливою для сортування великих масивів.
Сортування злиттям
Сортування злиттям, як правило, застосовуються в тих випадках, коли вимагається відсортувати послідовний файл, що не поміщається в основній пам'яті.
Один з популярних алгоритмів внутрішнього сортування із злиттям заснований на наступних ідеях (для простоти вважатимемо, що кількість елементів в масиві, як і в нашому прикладі, є ступенем числа 2). Спочатку пояснимо, що таке злиття.
Нехай є два відсортованих у порядку зростання масиви p[1], p[2], ..., p[n] і q[1], q[2], ..., q[n] і є порожній масив r[1], r[2], ..., r[2*n], який ми хочемо заповнити значеннями масивів p і q у порядку зростання. Для злиття виконуються наступні дії: порівнюються p[1] і q[1], і менше із значень записується в r[1]. Припустимо, що це значення p[1]. Тоді p[2] порівнюється з q[1], і менше із значень заноситься в r[2]. Припустимо, що це значення q[1]. Тоді на наступному кроці порівнюються значення p[2] і q[2] і т.д., поки ми не досягнемо меж одного з масивів. Тоді залишок іншого масиву просто дописується в «хвіст» масиву r.
Алгоритм сортуванням злиттям подано на рис. 6.19.
Для сортування із злиттям масиву а[1], а[2], ..., а[n] додається парний масив b[1], b[2], ..., b[n]. На першому кроці здійснюється злиття а[1] і а[n] з розміщенням результату в b[1], b[2], злиття а[2] і а[n-1] з розміщенням результату в b[3], b[4], ..., злиття а[n/2] і а[n/2+1] з розміщенням результату в b[n-1], b[n]. На другому кроці здійснюється злиття пар b[1], b[2] і b[n-1], b[n] з розміщенням результату в а[1], а[2], а[3], а[4], злиття пар b[3], b[4] і b[n-3], b[n-2] з розміщенням результату в а[5], а[6], а[7], а[8], ..., злиття пар b[n/2-1], b[n/2] і b[n/2+1], b[n/2+2] з розміщенням результату в а[n-3], а[n-2], а[n-1], а[n]. І т.д. На останньому кроці, наприклад (залежно від значення n), здійснюється злиття послідовностей елементів масиву завдовжки n/2 а[1], а[2], ..., а[n/2] і а[n/2+1], а[n/2+2], ..., а[n] з приміщенням результату в b[1], b[2], ..., b[n].
Для випадку масиву, що використовується в наших прикладах, послідовність кроків показана в таблиці 9.

Рис. 6.19. Блок-схема методу сортування злиттям
Таблиця 9. Приклад сортування злиттям
Початковий стан масиву
8 23 5 65 44 33 1 6

Крок 1
6 8 1 23 5 33 44 65

Крок 2
6 8 44 65 1 5 23 33

Крок 3
1 5 6 8 23 33 44 65

При застосуванні сортування із злиттям кількість порівнянь ключів і кількість пересилань оцінюється як Про(n*log n). Але слід враховувати, що для виконання алгоритму для сортування масиву розміру n потрібен 2n елементів пам'яті.
Методи порозрядного сортування
Розглянутий нижче алгоритм істотно відрізняється від описаних раніше.
По-перше, він зовсім не використовує порівнянь сортованих елементів.
По-друге, ключ, за яким відбувається сортування, необхідно розділити на частини, розряди ключа. Наприклад, слово можна розділити по буквах, число – по цифрах..
До сортування необхідно знати два параметри: k і m, де
k – кількість розрядів у самому довгому ключі,
m – розрядність даних: кількість можливих значень розряду ключа
При сортуванні українських слів m = 33, тому що буква може приймати не більш 33 значень. Якщо в найдовшому слові 10 букв, k = 10.
Аналогічно, для шістнадцяткових чисел m=16, якщо як розряд брати цифру, і m=256, якщо використовувати побайтовий поділ.
Ці параметри не можна змінювати в процесі роботи алгоритму. У цьому – ще одна відмінність методу від вищеописаних.
Порозрядне сортування для списків
Припустимо, що елементами лінійного списку L є k-розрядні десяткові числа, розрядність максимального числа відома заздалегідь. Позначимо d(j,n) – j-а права цифра числа n, яку можна виразити як d(j,n) = [ n / 10j-1 ] % 10.
Нехай L0, L1,..., L9 – допоміжні списки (кишені), спочатку порожні. Поразрядне сортування складається з двох процесів, які називаються розподіл і збір, і виконуються для j=1,2,...,k.
Фаза розподілу розносить елементи L по кишенях: елементи li списку L послідовно додаються в списки Lm, де m = d(j, li). Таким чином одержуємо десять списків, у кожному з який j-ті розряди чисел однакові і рівні m.
Фаза збору полягає в об'єднанні списків L0, L1,..., L9 у загальний список
L = L0 => L1 => L2 => ... => L9.
Розглянемо приклад роботи алгоритму на вхідному списку
0 => 8 => 12 => 56 => 7 => 26 => 44 => 97 => 2 => 37 => 4 => 3 => 3 => 45 => 10.
Максимальне число містить дві цифри, отже, розрядність даних k=2.
Перший прохід, j=1.
    Розподіл за першою праворуч цифрою:
L0:0 => 10        // усі числа з першою правою цифрою 0
L1: порожньо
L2:12 => 2
L3:3 => 3
L4:44 => 4
L5:45
L6:56 => 26
L7:7 => 97 => 37
L8:8
L9: порожньо         // усі числа с першою правою цифрою 9
   
 Збір:
з'єднуємо списки Li один за одним
L: 0 => 10 => 12 => 2 => 3 => 3 => 44 => 4 => 45 => 56 => 26 => 7 => 97 => 37 => 8
Другий прохід, j=2.
    Розподіл за другою цифрою справа:
L0:0 => 2 => 3 => 3 => 4 => 7 => 8
L1:10 => 12
L2:26
L3:37
L4:44 => 45
L5:56
L6: порожньо
L7: порожньо
L8: порожньо
L9:97
   
 Збір:
з'єднуємо списки Li один за іншим
L: 0 => 2 => 3 => 3 => 4 => 7 => 8 => 10 => 12 => 26 => 37 => 44 => 45 => 56 => 97

Рис. 6.20. Алгоритм порозрядного сортування.
Кількість використаних кишень – кількість можливих значень елемента списку.
Сортування можна організувати таким чином, щоб не використовувати додаткової пам'яті для кишень, тобто елементи списку не переміщати, а за допомогою перестановки вказівників приєднувати їх до тієї чи іншої кишені.
  Порозрядне сортування для масивів
Списки досить зручні тим, що їх легко реорганізовувати, поєднувати і т.ін. Як застосувати ту ж ідею для масивів?
Нехай у нас є масив source з n десяткових цифр ( m = 10 ).
Наприклад, source[7] = { 7, 9, 8, 5, 4, 7, 7 }, n=7. Тут покладемо const k=1.
1. Створити масив count з m елементів(лічильників).
2. Присвоїти кількість елементів source, рівних і. Для цього:
проініціалізувати count[] нулями,
пройти по source від початку до кінця, для кожного числа збільшуючи елемент count з відповідним номером.
for( i=0; i<n; i++) count [ source[i] ]++
У нашому прикладі count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }
3. Присвоїти count[i] значення, рівні сумі всіх елементів до даного:
count[i] = count[0]+count[1]+...count[і-1].
У нашому прикладі count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }
Ця сума є кількістю чисел вихідного масиву, менших i.
4. Зробити остаточне розміщення.
Для кожного числа source[i] ми знаємо, скільки чисел є менші за нього – це значення зберігається в count[source[i] ]. Таким чином, нам відомо остаточне місце числа в упорядкованому масиві: якщо є K чисел менших заданого, то воно повинне стояти на позиції K+1.
Здійснюємо прохід по масиву source зліва направо, одночасно заповнюючи вихідний масив dest:
for ( i=0; i<n; i++ ) {
c = source[i];
dest[ count[c] ] = c;
count[c]++; // для повторюваних чисел
}
Таким чином, число c=source[і] ставиться на місце count[c]. На цей випадок, якщо числа повторюються в масиві, передбачений оператор count[c]++, що збільшує значення позиції для наступного числа c, якщо таке буде.
Цикли займають (n + m) часу. Стільки ж потрібно пам'яті.
Отже, ми навчилися за (n + m) сортувати цифри. Аналогічно продемонструємо сортування для рядків (чисел). Нехай у нас в кожнім ключі k цифр (m = 10). Аналогічно до випадку зі списками відсортуємо їх у кілька проходів від молодшого розряду до старшого.
Вихідна k=3
послідовність
Перший прохід по 3-му розряду
Другий прохід по 2-му розряду
Третій прохід по 1-му розряду

523
153
088
554
235
523
153
554
235
088
523
235
153
554
088
088
153
235
523
554

Загальна кількість операцій, таким чином, (k(n+m)), при використовуваній додатково пам'яті (n+m). Ця схема допускає невелику оптимізацію. Помітимо, що сортування по кожнім байті складається з 2 проходів по всьому масиві: на першому кроці і на четвертому. Однак, можна створити відразу всі масиви count[] (по одному на кожну позицію) за один прохід.
Таким чином, перший крок буде виконуватися один раз за все сортування, а виходить, загальна кількість проходів зміниться з 2k на k+1.
Ефективність порозрядного сортування
Ріст швидкого сортування: O(nlogn). Судячи з оцінки, порозрядне сортування росте лінійним чином по n, оскільки що k,m – константи.
Також воно росте лінійним чином по k – при збільшенні довжини типу (кількості розрядів) відповідно зростає кількість проходів. Однак, в останній пункт реальні умови вносять свої корективи.
Справа в тому, що основний цикл сортування по i-му байті проходить по вказівнику uchar* bp з кроком sizeof(T) у масиві для одержання чергового розряду. Коли T=char, крок дорівнює 1, T=short – крок дорівнює 2, T=long – крок дорівнює 4... Чим більший розмір типу, тим менш послідовний доступ до пам'яті здійснюється, а це дуже істотно для швидкості роботи. Тому реальний час зростає набагато швидше, ніж теоретичний.
Крім того, порозрядне сортування вже по своїй суті нецікаве для малих масивів. Кожен прохід містить мінімум 256 ітерацій, тому при невеликих n загальний час виконання (n+m) визначається константою m=256.
Методи зовнішнього сортування
Прийнято називати «зовнішнім» сортуванням сортування послідовних файлів, розташованих в зовнішній пам'яті і дуже великих, щоб можна було цілком перемістити їх в основну пам'ять і застосувати один з розглянутих в попередньому розділі методів внутрішнього сортування. Найчастіше зовнішнє сортування застосовується в системах управління базами даних при виконанні запитів, і від ефективності вживаних методів істотно залежить продуктивність СУБД.
Слід пояснити, чому йдеться саме про послідовні файли, тобто про файли, які можна читати запис за записом в послідовному режимі, а писати можна тільки після останнього запису. Методи зовнішнього сортування з'явилися, коли найбільш поширеними пристроями зовнішньої пам'яті були магнітні стрічки. Для стрічок чисто послідовний доступ був абсолютно природним. Коли відбувся перехід до пристроїв, що запам'ятовують, з магнітними дисками, що забезпечують "прямий" доступ до будь-якого блоку інформації, здавалося, що чисто послідовні файли втратили свою актуальність. Проте це припущення було помилковим.
Вся річ у тому, що практично всі використовувані в даний час дискові пристрої забезпечені рухомими магнітними головками. При виконанні обміну з дисковим накопичувачем виконується підведення головок до потрібного циліндра, вибір потрібної головки (доріжки), прокрутка дискового пакету до початку необхідного блоку і, нарешті, читання або запис блоку. Серед всіх цих дій найбільший час займає підведення головок. Саме цей час визначає загальний час виконання операції. Єдиним доступним прийомом оптимізації доступу до магнітних дисків є якомога "ближче" розташування на накопичувачі блоків файлу, що послідовно адресуються. Але і в цьому випадку рух головок буде мінімізоване тільки у тому випадку, коли файл читається або пишеться в чисто послідовному режимі. Саме з такими файлами при потребі сортування працюють сучасні СУБД.
Слід також помітити, що насправді швидкість виконання зовнішнього сортування залежить від розміру буфера (або буферів) основної пам'яті, яка може бути використана для цих цілей.
Пряме злиття
Припустимо, що є послідовний файл А, що складається із записів a1, a2, ..., an (знову для простоти припустимо, що n є ступінь числа 2). Вважатимемо, що кожен запис складається рівно з одного елементу, що є ключ сортування. Для сортування використовуються два допоміжні файли B і С (розмір кожного з них буде n/2).
Сортування складається з послідовності кроків, в кожному з яких виконується розподіл стану файлу А у файли B і С, а потім злиття файлів B і С у файл А. (Помітимо, що процедура злиття для файлів повністю ілюструється рисунком 14.) На першому кроці для розподілу послідовно читається файл А, і записи a1, a3, ..., а(n-1) пишуться у файл B, а записи a2, a4, ..., an – у файл С (початковий розподіл). Початкове злиття здійснюється над парами (a1, a2), (a3, a4), ..., (а(n-1), an), і результат записується у файл А. На другому кроці знову послідовно читається файл А, і у файл B записуються послідовні пари з непарними номерами, а у файл С – з парними. При злитті утворюються і пишуться у файл А впорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл А міститиме дві впорядковані підпослідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл B, а друга - у файл С. Після злиття файл А міститиме повністю впорядковану послідовність записів. У таблиці 10 показаний приклад зовнішнього сортування простим злиттям. Помітимо, що для виконання зовнішнього сортування методом прямого злиття в основній пам'яті вимагається розташувати всього лише дві змінні – для розміщення чергових записів з файлів B і С.
Природне злиття
При використанні методу прямого злиття не береться до уваги те, що початковий файл може бути частковий відсортованим, тобто містити впорядковані підпослідовності записів. Серією називається підпослідовність записів ai, а(i+1), ..., aj така, що ak <= а(k+1) для всіх i <= до < j, ai < а(i-1) і aj > а(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті.
Таблиця 10. Приклад зовнішнього сортування прямим злиттям
Початковий стан файлу А
8 23 5 65 44 33 1 6

Перший крок
Розподіл
Файл B
Файл С



8 5 44 1


23 65 33 6

Злиття: файл А
8 23 5 65 33 44 1 6

Другий крок
Розподіл


Файл B
8 23 33 44

Файл С
5 65 1 6

Злиття: файл А
5 8 23 65 1 6 33 44

Третій крок
Розподіл


Файл B
5 8 23 65

Файл С
1 6 33 44

Злиття: файл А
1 5 6 8 23 33 44 65

Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файлу А по файлам B і С, а потім злиття B і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл B, друга – у файл С і т.д. При злитті перша серія записів файлу B зливається з першою серією файлу С, друга серія B з другою серією С і т.д. Якщо проглядання одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файлу цілком копіюється в кінець файлу А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файлу показаний на рис. 6.21 і 6.22.

Рис. 6.21. Зовнішнє пряме сортування злиттям. Перший крок.

Рис. 6.22. Зовнішнє пряме сортування злиттям. Другий крок.
Очевидно, що кількість зчитувань/перезаписів файлів при використанні цього методу буде не гірша, ніж при застосуванні методу прямого злиття, а в середньому – краща. З другого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, то максимальний розмір файлів B і С може бути близький до розміру файлу А.
Збалансоване багатошляхове злиття
У основі методу зовнішнього сортування збалансованим багатошляховим злиттям є розподіл серій початкового файлу по m допоміжним файлам B1, B2, ..., Bm і їх злиття в m допоміжних файлів C1, C2, ..., Cm. На наступному кроці здійснюється злиття файлів C1, C2, ..., Cm у файли B1, B2, ..., Bm і т.д., поки в B1 або C1 не утворюється одна серія.
Багатошляхове злиття є природним розвитком ідеї звичного (двошляхового) злиття, ілюстрованого рис. 6.22. Приклад тришляхового злиття показаний на рис. 6.23.
На рис. 6.24 показаний простий приклад застосування сортування багатошляховим злиттям. Він, зазвичай, дуже тривіальний, щоб продемонструвати декілька кроків виконання алгоритму, проте достатній як ілюстрація загальної ідеї методу. Помітимо, що, як показує цей приклад, у міру збільшення довжини серій допоміжні файли з великими номерами (починаючи з номера n) перестають використовуватися, оскільки їм «не дістається» жодної серії. Перевагою сортування збалансованим багатошляховим злиттям є те, що кількість проходів алгоритму оцінюється як Про(log n) (n – кількість записів в початковому файлі), де логарифм береться по n. Порядок кількості копіювань записів - (log n). Зазвичай, кількість порівнянь не буде меншою, ніж при застосуванні методу простого злиття.
Багатофазне сортування
При використанні розглянутого вище за метод збалансованого багатошляхового зовнішнього сортування на кожному кроці приблизно половина допоміжних файлів використовується для введення даних і приблизно стільки ж для виведення злитих серій. Ідея багатофазного сортування полягає у тому, що з наявних m допоміжних файлів (m-1) файл служить для введення злитих послідовностей, а один - для виведення утворюваних серій. Як тільки один з файлів введення стає порожнім, його починають використовувати для виведення серій, одержуваних при злитті серій нового набору (m-1) файлів. Таким чином, є перший крок, при якому серії початкового файлу розподіляються по m-1 допоміжному файлу, а потім виконується багатошляхове злиття серій з (m-1) файлу, поки в одному з них не утворюється одна серія.

Рис. 6.23.

Рис. 6.24.
Очевидно, що при довільному початковому розподілі серій по допоміжним файлам алгоритм може не зійтися, оскільки в єдиному непорожньому файлі існуватиме більш, чим одна серія. Припустимо, наприклад, що використовується три файли B1, B2 і B3, і при початковому розподілі у файл B1 поміщені 10 серій, а у файл B2 - 6. При злитті B1 і B2 до моменту, коли ми дійдемо до кінця B2, в B1 залишаться 4 серії, а в B3 потраплять 6 серій. Продовжиться злиття B1 і B3, і при завершенні перегляду B1 в B2 міститимуться 4 серії, а в B3 залишаться 2 серії. Після злиття B2 і B3 в кожному з файлів B1 і B2 міститиметься по 2 серії, яка злитиметься і утворюють 2 серії в B3 при тому, що B1 і B2 – порожні. Тим самим, алгоритм не зійшовся (таблиця 11).
Таблиця 11. Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не приводить до потрібного результату
К-сть серій у файлі B1
К-сть серій у файлі B2
К-сть серій у файлі B3

10
6
0

4
0
6

0
4
2

2
2
0

0
0
2


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