Анотація: В лекції розглядаються визначення та класифікація алгоритмів сортувань масивів, зокрема, швидких угруповань, вивчаються параметри, що характеризують трудомісткість алгоритмів сортувань, розглядаються опису і приклади програмних кодів наступних алгоритмів швидких угруповань: бінарна пірамідальна сортування, сортування злиттям, сортування Шелла і сортування Хоара.
Мета лекції. вивчити основні алгоритми внутрішніх угруповань і навчитися вирішувати завдання угруповань масивів різними методами (бінарна пірамідальна сортування. метод Шелла, швидке сортування Хоара, сортування злиттям).
Сортування є однією з фундаментальних алгоритмічних задач програмування. Вирішенню проблем, пов'язаних з сортуванням, присвячено безліч наукових досліджень, розроблено безліч алгоритмів.
У загальному випадку сортування слід розуміти як процес перегрупування заданої множини об'єктів в певному порядку. Сортування застосовується у всіх без винятку областях програмування, будь то бази даних або математичні програми.
Алгоритмом сортування називається алгоритм для упорядкування деякої множини елементів. Зазвичай під алгоритмом сортування увазі алгоритм упорядкування безлічі елементів за зростанням або спаданням.
У разі наявності елементів з однаковими значеннями, у впорядкованій послідовності вони розташовуються поруч один за одним в будь-якому порядку. Однак іноді буває корисно зберігати первісний порядок елементів з однаковими значеннями.
В алгоритмах сортування лише частина даних використовується в якості ключа сортування. Ключем сортування називається атрибут (або кілька атрибутів), за значенням якого визначається порядок елементів. Таким чином, при написанні алгоритмів сортувань масивів слід врахувати, що ключ повністю або частково збігається з даними.
Практично кожен алгоритм сортування можна розбити на 3 частини:
- порівняння, що визначає впорядкованість пари елементів;
- перестановку. міняє місцями пару елементів;
- власне сортують алгоритм, який здійснює порівняння і перестановку елементів до тих пір, поки всі елементи множини не будуть упорядковані.
Алгоритми сортування мають велике практичне застосування. Їх можна зустріти там, де мова йде про обробку та зберігання великих обсягів інформації. Деякі завдання обробки даних вирішуються простіше, якщо дані заздалегідь упорядкувати.
Оцінка алгоритмів сортування
Жодна інша проблема не породила такої кількості найрізноманітніших рішень, як завдання сортування. Універсального, найкращого алгоритму сортування на даний момент не існує. Однак, маючи приблизні характеристики вхідних даних. можна підібрати метод, який працює оптимальним чином. Для цього необхідно знати параметри, за якими буде проводитися оцінка алгоритмів.
- Час сортування - основний параметр, що характеризує швидкодію алгоритму.
- Пам'ять - один з параметрів, який характеризується тим, що ряд алгоритмів сортування вимагають виділення додаткової пам'яті під тимчасове зберігання даних. При оцінці використовуваної пам'яті не буде враховуватися місце, яке займає вихідний масив даних і не залежать від вхідної послідовності витрати, наприклад, на зберігання коду програми.
- Стійкість - це параметр, який відповідає за те, що сортування не змінює взаємного розташування рівних елементів.
- Природність поведінки - параметр, якій вказує на ефективність методу при обробці вже відсортованих, або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
Класифікація алгоритмів сортувань
Все розмаїття і різноманіття алгоритмів сортувань можна класифікувати за різними ознаками, наприклад, за стійкістю, з поведінки, по використанню операцій порівняння, за потреби у додатковій пам'яті, за потребою в знаннях про структуру даних, що виходять за рамки операції порівняння, та інші.
Найбільш докладно розглянемо класифікацію алгоритмів сортування за сферою застосування. В даному випадку основні типи впорядкування діляться наступним чином.
- Внутрішня сортування - це алгоритм сортування, який в процесі упорядкування даних використовує тільки оперативну пам'ять (ОЗП) на комп'ютері. Тобто оперативної пам'яті досить для розміщення в ній сортованого масиву даних з довільним доступом до будь-якому осередку і власне для виконання алгоритму. Внутрішня сортування застосовується у всіх випадках, за винятком однопрохідного зчитування даних і однопрохідної записи відсортованих даних. Залежно від конкретного алгоритму і його реалізації дані можуть сортуватися в тій же області пам'яті, або використовувати додаткову оперативну пам'ять.
- Зовнішня сортування - це алгоритм сортування, який при проведенні упорядкування даних використовує зовнішню пам'ять. як правило, жорсткі диски. Зовнішня сортування розроблена для обробки великих списків даних, які не поміщаються в оперативну пам'ять. Звернення до різних носіїв накладає деякі додаткові обмеження на даний алгоритм: доступ до носія здійснюється послідовним чином, тобто в кожен момент часу можна вважати або записати тільки елемент, наступний за поточним; обсяг даних не дозволяє їм розміститися в ОЗУ.
Внутрішня сортування є базовою для будь-якого алгоритму зовнішньої сортування - окремі частини масиву даних упорядковано в оперативній пам'яті і за допомогою спеціального алгоритму зчіплюються в один масив. упорядкований по ключу.
Слід зазначити, що внутрішня сортування значно ефективніше зовнішньої, так як на звернення до оперативної пам'яті витрачається набагато менше часу, ніж до носіїв.
Розглянемо основні алгоритми внутрішніх угруповань, які називаються вдосконаленими (логарифмічними).
Бінарна пірамідальна сортування
Даний метод сортування був запропонований Дж. У. Дж. Вільямсом і Р.У. Флойдом в 1964 році. Пірамідальна сортування в деякому роді є модифікацією такого підходу, як сортування вибором. з тією лише відмінністю, що мінімальний (або максимальний) елемент з невідсортоване послідовності вибирається за меншу кількість операцій. Для такого швидкого вибору з цієї невідсортоване послідовності будується деяка структура. Саме суть даного методу і полягає в побудові такої структури, яка називається пірамідою.
Піраміда (вбиральня дерево, бінарна купа) - бінарне дерево з впорядкованими листям (корінь дерева - найменший чи найбільший елемент). Піраміду можна представити у вигляді масиву. Перший елемент піраміди є найменшим або найбільшим, що залежить від ключа сортування.
Просіювання - це побудова нової піраміди за наступним алгоритмом: новий елемент поміщається в вершину дерева, далі він переміщається ( "просівається") по шляху вниз на основі порівняння з дочірніми елементами. Спуск завершується, якщо результат порівняння з дочірніми елементами відповідає ключу сортування.
Послідовність чисел xi, xi + 1. xn формує піраміду. якщо для всіх k = i, i + 1. n / 2 виконуються нерівності xk> x2k. xk> xi (або xk Масив чисел 12 10 7 5 8 7 3 є пірамідою. Такий масив зручно зображувати у вигляді дерева. Перший елемент масиву, елементи якого утворюють собою піраміду. є найбільшим (або найменшим). Якщо масив представлений у вигляді піраміди. то масив легко впорядкувати. Алгоритм пірамідальної сортування. Крок 1. Перетворити масив в піраміду (рис. 42.1. А).Схожі статті