Алгоритм сортування — це послідовність інструкцій, яка приймає на вхід масив (іноді званий списком), виконує над ним певні операції та повертає відсортований масив. Алгоритми сортування часто вивчають на початку курсів з комп’ютерних наук, оскільки вони є простим способом ознайомлення з іншими ключовими темами, як-от нотація Big-O, методи «розділяй і володарюй» та структури даних (бінарні дерева, купи тощо). При виборі алгоритму сортування слід враховувати багато факторів.
Зміст
- Алгоритми сортування
- Властивості алгоритмів сортування
- Поширені алгоритми сортування
- Вибір алгоритму сортування
- Дивіться також
- Джерела
Алгоритми сортування
Інакше кажучи, відсортований масив — це масив, елементи якого розташовані в певному порядку. Наприклад, $[a, b, c, d]$ відсортовано за алфавітом, $[1, 2, 3, 4, 5]$ — це список цілих чисел у порядку зростання, а $[5, 4, 3, 2, 1]$ — у порядку спадання.
Алгоритм сортування отримує масив на вхід і видає відсортовану перестановку цього масиву.
Існує два основних типи алгоритмів сортування: сортування порівнянням та цілочисельне сортування.
Сортування порівнянням (Comparison Sorts)
Алгоритми сортування порівнянням на кожному кроці зіставляють елементи між собою, щоб визначити, чи має один елемент стояти ліворуч чи праворуч від іншого.
Такі алгоритми зазвичай простіші в реалізації, ніж цілочисельні, проте вони обмежені нижньою межею $\Omega(n \log n)$. Це означає, що в середньому сортування порівнянням не може працювати швидше за $O(n \log n)$. Нижня межа алгоритму — це час виконання в найгіршому випадку для найкращого можливого алгоритму розв’язання даної задачі.
Фраза «в середньому» тут важлива: існує багато алгоритмів, які працюють дуже швидко, якщо вхідний список уже відсортований або має певну специфічну (і загалом малоймовірну) властивість. Оскільки існує лише одна відсортована перестановка списку з $n!$ можливих, шанси на те, що вхідні дані вже впорядковані, вкрай низькі.
Час виконання алгоритмів сортування на основі порівняння обмежений значенням $\Omega(n \log n)$.
Сортування порівнянням можна моделювати як велике бінарне дерево, зване деревом рішень, де кожен вузол представляє одне порівняння. Для списку довжиною $n$ існує $n!$ можливих перестановок. Кожна з них представлена «листком» дерева, а шлях до кожного листка — це послідовність порівнянь та їхніх результатів.
На кожному рівні дерева відбувається порівняння. Ми рухаємося вниз, доки не досягнемо листків. Оскільки для кожної перестановки є свій листок, усього їх $n!$. Кожне порівняння вдвічі зменшує кількість майбутніх порівнянь. Будь-яке бінарне дерево висотою $h$ має кількість листків, що не перевищує $2^h$.
Звідси:
$$2^h \geq n!$$
Взявши логарифм, отримуємо:
$$h \geq \log(n!)$$
За апроксимацією Стірлінга:
$$n! > \left(\frac{n}{e}\right)^n$$
Отже:
$$h \geq \log\left(\frac{n}{e}\right)^n = n\log \left(\frac{n}{e}\right) = n\log n - n \log e = \Omega(n\log n)$$
Цілочисельне сортування (Integer Sorts)
Цілочисельні сортування іноді називають сортуванням підрахунком (хоча існує конкретний алгоритм із такою назвою). Вони не використовують порівняння, тому не обмежені межею $\Omega(n \log n)$. Такі алгоритми визначають для кожного елемента $x$, скільки елементів менше за нього. Якщо таких елементів 14, то $x$ одразу ставиться на 15-ту позицію. Ця інформація дозволяє миттєво розмістити елементи у правильні комірки без перестановки списків.
Властивості алгоритмів сортування
Усі алгоритми сортування мають спільну мету, але методи її досягнення різняться. Працюючи з будь-яким алгоритмом, важливо знати його часову та просторову складність.
Як було показано вище, часова складність сортувань порівнянням становить $\Omega(n \log n)$. Зазвичай швидкість обговорюють у термінах Big O. Наприклад, якщо алгоритм має складність $O(n \log n)$ у найгіршому випадку, це гарантує, що він ніколи не працюватиме повільніше за цей показник.
Часова складність описує кількість операцій, які має виконати алгоритм.
Просторова складність описує обсяг пам’яті, необхідний для роботи. Наприклад, якщо алгоритм приймає список розміру $n$ і створює новий список розміру $n$ для кожного елемента, йому знадобиться $n^2$ пам’яті.