3.1 Представлення методів сортування.

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

- сортування за допомогою включення (by insertion);

- сортування за допомогою виділення (by selection);

- сортування за допомогою обмінів (by exchange).

Двома найбільш важливими програмними аспектами є об’єм машинного часу, необхідний для роботи програми сортування, і об’єм пам’яті, необхідний для цієї програми . Доброю мірою ефективності може бути число необхідних порівнянь та число перестановок елементів масиву. Ці величини є функціями від числа елементів n, які сортуються. Ефективні алгоритми сортування потребуються порядку nlog n2порівнянь. В простих і очевидних методах, які називають прямими, потрібно порядку n 2 порівнянь .

Для розгляду алгоритмів сортування доцільно ввести деяке умовне позначення. Якщо є елементи a ,a ,...,a 1 2 n, то сортуванням є перестановка цих елементів до одержання масиву a ,a ,...,a 1 2 n, в якому при деякій функції впорядкування f виконується відношення f(aʳ 1) ≤ f(aʳ 2) ≤ ...≤ f(aʳ n).

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

Найпростіший метод сортування називається бульбашковим сортуванням: на першому проході сусідні елементи порівнюються і якщо елементи не впорядковані, вони змінюються місцями, в результаті чого найбільший із тих, що залишились (порівняння іде між (n-1) елементами), переміщується на передостаннє місце і так до тих пір, поки масив не виявиться впорядкованим [5]. Основна перевага бульбашкового методу сортування – це те, що його легко реалізувати у вигляді програми.

Недолік цього методу полягає в тому, що він володіє незначною швидкодією [1].

Найбільш істотного покращення можна досягти, використовуючи сортування Шела (або сортування з кроком, що зменшується). В цьому методі в першопочатковому масиві сортуються окремі під масиви. При цьому К називається кроком n, наприклад, якщо К рівне 5, то першим сортується підмасив, який складається з елементів а(1), а(6), а(11) і т.д. П’ять підмасивів кожен з яких містить 1/5 елементів початкового масиву, сортуються аналогічним чином [1].

При швидкому сортуванні за методом Хоара масив переглядається одразу з двох боків. Якщо з одного боку знаходиться елемент більший, ніж з іншого, то ці елементи змінюються місцями. Так продовжується до того часу, поки вказівники на лівий і правий елементи не перетнуться. В результаті такого проходження алгоритму весь масив розбитий на дві частини. В лівій частині знаходяться елементи з меншими значеннями ключів, а в правій – з більшими. Тепер залишається відсортувати тим самим методом кожну частину окремо [3].

При сортуванні методом підрахунку кожен елемент порівнюється з усіма іншими елементами. Якщо який-небудь елемент більший, ніж К елементів цього масиву, то після впорядкування він повинен займати (К+1) місце, відповідно, необхідно порівняти попарно всі ключі та підрахувати, скільки з них менше кожного окремого ключа. Після цього необхідно переставити елементи у відповідності з певними місцями [6].

При сортуванні вставкою елементи переглядаються по одному і кожен новий елемент вставляється в підходяще місце серед раніше впорядкованих елементів [3]. Суть сортування простими вставками полягає в наступному: нехай на і-му кроці алгоритму послідовність з (і–1) перших елементів масиву впорядкована. Додавання і-го елементу в цю послідовність відбувається впорядковано: елемент, який потрібно вставити, порівнюється з попереднім до тих пір, поки не знайдеться місце і-го елемента [5].

Сортування простим вибором здійснюється так: спочатку з n елементів вибирається максимальний. Далі n-ний та знайдений максимальний елементи міняються місцями. Потім серед (n–1) елементів, що залишилися, від 1 до (n–1) вибирається максимальний і міняються місцями з елементом, який стоїться на (n–1)-му місці і т.д. [7]. Так продовжується до того часу, поки весь масив не буде відсортований. Останній раз максимум вибирається з двох елементів, які стоять на першому і на другому місці відповідно, і більший з них стає на друге місце [5].

Сортування за допомогою двійкового дерева пошуку, яке можна використовувати для сортування, виконується так: береться порожнє дерево, до нього додаються всі елементи масиву в порядку зростання [1]. Якщо елементи масиву різні та розміщені у випадковому порядку, а довжина масиву n, то алгоритм вимагає в середньому nlog n2операцій [10]. Якщо елементи відсортовані у порядку збільшення або порядку спадання, то дерево стає незбалансованим (тобто у нього з’являється багато порожніх гілок), і алгоритм вимагає 2n операцій [1].

Алгоритм сортування злиттям є процесом об’єднання двох або більш відсортованих файлів в деякий третій відсортований файл [8]. Нехай є два відсортованих масиви M i N, тоді порівнюються два найменші елементи обох масивів і найменший з них виводиться як найменший елемент сумарного масиву, потім процедура повторюється до тих пір, поки результуючий масив не буде відсортований злиттям.

Порівняння здійснювалось за такими характеристиками: кількість ітерацій (КІ), кількість порівнянь в ітерації (КПІ), загальна кількість порівнянь (ЗКП). Для кожного методу наведемо також переваги та недоліки.

1. Метод бульбашки (bubble) [1, 5].

Переваги: для поліпшеного сортування середнє число проходів (ітерацій) рівне n-k √n . Недоліки: середня кількість переміщень 3n(n-1)/2. Велика кількість обмінів при масиві зі зворотнім порядком [6].

2. Метод Шела (Shell) [1, 6].

Переваги: мінімальний об’єм пам’яті, скорочення повторних порівнянь. Недоліки: велике число обмінів при масиві зі зворотним порядком.

3. Метод лінійного вибору з підрахунком (linear choice with count) [3,6].

Переваги: можливість обрахувати адресу будь-якого елемента в списку виведення. Недоліки: необхідна додаткова пам’ять під список лічильників..

4. Метод лінійної вставки (linear insert) [2-5].

Переваги: всі елементи повинні бути відомі.Недоліки: виконується переміщення з однієї позиції в іншу, а не взаємний обмін; середня кількість переміщень (n² + 9n -10)/4.

5. Метод просіювання (лінійна вставка з обміном) (sifting) [3, 6].

Переваги: метод не зберігає фіксовану послідовність порівнянь. Недоліки: велике число обмінів при списку в зворотному порядку.

6. Метод швидкого сортування, або метод Хоара (quick sort) [4, 5].

В кращому випадку , в гіршому – .

Переваги: в метод можна легко включити будь-який метод сортування. Недоліки: недостатньо висока продуктивність при невеликих n.

7. Метод простого вибору (simple choice) [1, 5, 8].

Переваги: метод не вимагає використання додаткової пам’яті. Недоліки: середня кількість переміщень n(lnn+g), де g =0,577216 – постійна Ейлера. Час сортування збільшується квадратично відносно кількості елементів. Метод характеризується нестійкістю [8].

8. Метод підрахунку (calculation) [5, 10].

Недоліки: кількість переміщень 9n /4. Вимагає додаткової пам’яті.

9. Метод бінарного дерева (binary tree) [1, 3, 10].

Переваги: мінімальна кількість рівнів та мінімальний об’єм. Недоліки: вимагає додаткової пам’яті; немає можливості точно передбачати потрібний об’єм пам’яті.

10. Метод простого злиття (simple merge) [1,9, 10].

Недоліки: потребує додаткову пам’ять; доступ до даних відбувається набагато повільніше, ніж при використанні інших методів.

11. Метод сортування з обчисленням адреси (sorting with calculation of address) [1, 10].

Переваги: велика швидкодія. Недоліки: порядок елементів в масиві не збігається з їх порядком в списку; складність здійснення динамічнерозширення масиву.

12. Метод пірамідального сортування (heap sort) [7].

Переваги: не потребує додаткової пам’яті. Недоліки: метод характеризується нестійкістю.

13. Метод порозрядного сортування (radix sort) [1, 9].

Переваги: найбільш підходить для використання в комп’ютерній графіці; списки легко реорганізовувати, об’єднувати. Недоліки: вимагає додаткову пам’ять [10].

14. Метод парного обміну (pair exchange) [3, 6].

В кращому випадку , в гіршому .

Переваги: найвища ефективність при використанні у вигляді мережі для паралельних процесорів. Недоліки: потребує додаткових витрат на управління парними-непарними переглядами; великий об’єм пам’яті під процедури і низька швидкодія.

15. Метод турнірного сортування (tournament sorting) [1, 8].

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