Алгоритм сортування - це алгоритм для впорядкування елементів в списку. У разі, коли елемент списку має кілька полів, поле, що служить критерієм порядку, називається ключем сортування. На практиці в якості ключа часто виступає число, а в інших полях зберігаються будь-які дані, які не впливають на роботу алгоритму.
формулювання завдання
,
Будемо вважати, що з кожним елементом (крім іншої інформації, що не впливає на сортування) пов'язаний ключ. На безлічі ключів задано відношення порядку лінійно (або досконалого) упорядкування. для якого були б виконані наступні умови:
закон трихотомії. для будь-яких або, або, або;
транзитивність. для будь-яких якщо і, то.
Завданням сортування по неубиванія є знаходження перестановки елементів з індексами від, при якій ключі розташовуються в порядку неспадання:
В результаті роботи алгоритму і застосування перестановки виходить відсортований масив:
Аналогічно можна визначити сортування по незростання.
Оцінка алгоритму сортування
Алгоритми сортування оцінюються за швидкістю виконання та ефективності використання пам'яті:
Час - основний параметр, що характеризує швидкодію алгоритму. Називається також обчислювальною складністю. Для упорядкування важливі найгірше. середнє і краще поведінка алгоритму в термінах потужності вхідного безлічі A. Якщо на вхід алгоритму подається безліч A. то позначимо n = | A |. Для типового алгоритму хорошу поведінку - це O (n log n) і погану поведінку - це O (n 2). Ідеальну поведінку для упорядкування - O (n). Алгоритми сортування, що використовують тільки абстрактну операцію порівняння ключів завжди потребують щонайменше в Ω (n log n) порівняннях. Проте, існує алгоритм сортування Хана (Yijie Han) з обчислювальною складністю O (n log log n log log log n), який використовує той факт, що простір ключів обмежена (він надзвичайно складний, а за Про -позначення ховається вельми великий коефіцієнт, що унеможливлює його застосування в повсякденній практиці). Також існує поняття сортують мереж. Припускаючи, що можна одночасно (наприклад, при паралельному обчисленні) проводити кілька порівнянь, можна впорядкувати n чисел за O (log 2 n) операцій. При цьому число n має бути заздалегідь відомо;
Пам'ять - ряд алгоритмів вимагає виділення додаткової пам'яті під тимчасове зберігання даних. Як правило, ці алгоритми вимагають O (log n) пам'яті. При оцінці не враховується місце, яке займає вихідний масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми (так як все це потребляетO (1)). Алгоритми сортування, що не споживають додаткової пам'яті, відносять до сортувань на місці.
Властивості і класифікація
Стійкість (англ. Stability) - стійка сортування не змінює взаємного розташування елементів з однаковими ключами [3].
Природність поведінки - ефективність методу при обробці вже упорядкованих або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.
Використання операції порівняння. Алгоритми, що використовують для сортування порівняння елементів між собою, називаються заснованими на порівняннях. Мінімальна трудомісткість гіршого випадку для цих алгоритмів становить O (n log n), але вони відрізняються гнучкістю застосування. Для спеціальних випадків (типів даних) існують більш ефективні алгоритми.
Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:
Внутрішня сортування оперує масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь-якому осередку. Дані зазвичай упорядковуються на тому ж місці без додаткових витрат.
В сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.
Зовнішня сортування оперує запам'ятовують великого обсягу, але не з довільним доступом, а послідовним (впорядкування файлів), т. Е. В даний момент «видно» тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і призводить до спеціальних методів впорядкування, зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних у зовнішній пам'яті виробляється набагато повільніше, ніж операції з оперативною пам'яттю.
Доступ до носія здійснюється послідовним чином: в кожен момент часу можна вважати або записати тільки елемент, наступний за поточним.
Обсяг даних не дозволяє їм розміститися в ОЗУ.
Також алгоритми класифікуються за:
потреби в додатковій пам'яті або її відсутності
потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такої
Список алгоритмів сортування
У цій таблиці n - це кількість записів, які необхідно впорядкувати, а k - це кількість унікальних ключів.
Алгоритми стійкою сортування
Сортування вибором (Selection sort) - Складність алгоритму: O (n 2); пошук найменшого або найбільшого елемента і приміщення його в початок або кінець впорядкованого списку
Сортування бульбашкою (англ.Bubblesort) - складність алгоритму: O (n2); для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
Сортування перемішуванням (шейкерні, Cocktail sort, bidirectional bubble sort) - Складність алгоритму: O (n 2)
Сортування гнома - має спільне з сортуванням бульбашкою і сортуванням вставками. Складність алгоритму - O (n 2).
Сортування вставками (Insertion sort) - Складність алгоритму: O (n 2); визначаємо де поточний елемент повинен знаходитися в упорядкованому списку і вставляємо його туди
Сортування злиттям (Merge sort) - Складність алгоритму: O (n log n); потрібно O (n) додаткової пам'яті; вибудовуємо першу і другу половину списку окремо, а потім - зливаємо впорядковані списки
Сортування за допомогою двійкового дерева (англ.Treesort) - Складність алгоритму: O (n log n); потрібно O (n) додаткової пам'яті
Алгоритм сортування Timsort (англ.Timsort) - Складність алгоритму: O (n log n); потрібно O (n) додаткової пам'яті; Комбінований алгоритм (використовується сортування вставками і сортування злиттям. Розроблено для використання в мові Python [
Сортування підрахунком (Counting sort) - Складність алгоритму: O (n + k); потрібно O (n + k) додаткової пам'яті (розглянуто 3 варіанти)
Блокова сортування (корзину, Bucket sort) - Складність алгоритму: O (n); потрібно O (k) додаткової пам'яті і знання про природу сортируемих даних, що виходить за рамки функцій "переставити" і "порівняти".
Алгоритми нестійкою сортування
Сортування вибором (Selection sort) - Складність алгоритму: O (n 2); пошук найменшого або найбільшого елемента і приміщення його в початок або кінець впорядкованого списку
Сортування Шелла (Shell sort) - Складність алгоритму: O (n log 2 n); спроба поліпшити сортування вставками
Сортування гребінцем (Comb sort) - Складність алгоритму: O (n log n)
Пірамідальна сортування (Сортування купи, Heapsort) - Складність алгоритму: O (n log n); перетворюємо список в купу. беремо найбільший елемент і додаємо його в кінець списку
Плавне сортування (Smoothsort) - Складність алгоритму: O (n log n)
Швидке сортування (Quicksort), у варіанті з мінімальними витратами пам'яті - Складність алгоритму: O (n log n) - середній час, O (n 2) - найгірший випадок; широко відомий як найшвидший з відомих для упорядкування великих випадкових списків; з розбивкою вихідного набору даних на дві половини так, що будь-який елемент першої половини впорядкований щодо будь-якого елементу другої половини; потім алгоритм застосовується рекурсивно до кожної половині. При використанні O (n) додаткової пам'яті, можна зробити сортування стійкою.
Introsort - Складність алгоритму: O (n log n), поєднання швидкої і пірамідальної сортування. Пірамідальна сортування застосовується в разі, якщо глибина рекурсії перевищує log (n).
Patience sorting - Складність алгоритму: O (n log n) - найгірший випадок, вимагає додатково O (n) пам'яті, також знаходить найдовшу збільшується підпослідовність
Stooge sort - рекурсивний алгоритм сортування з тимчасової складністю.
Сортування за розрядами - Складність алгоритму: O (n · k); потрібно O (k) додаткової пам'яті.
Цифрова сортування - то ж, що і сортування за розрядами.
Непрактичні алгоритми сортування
Bogosort - O (n · n!) В середньому. Довільно перемішати масив, перевірити порядок.
Сортування перестановкою - O (n · n!) - найгірший час. Для кожної пари здійснюється перевірка вірного порядку і генеруються всілякі перестановки вихідного масиву.
Дурна сортування (Stupid sort) - O (n 3); рекурсивна версія вимагає додатково O (n 2) пам'яті
Bead Sort - O (n) or O (√n), потрібне спеціалізоване апаратне забезпечення
Блинная сортування (Pancake sorting) - O (n), потрібне спеціалізоване апаратне забезпечення
Алгоритми, які базуються на порівняннях
Блокова сортування (корзину, Bucket sort)
Лексикографічна або сортування за розрядами (Radix sort)
Сортування підрахунком (Counting sort)
Інші алгоритми сортування