Алгоритм сортування

Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.

Термінологія

Термін сортування (Шаблон:Lang-en) означає розділення елементів за певними ознаками (сортами) і не дуже точно описує поставлене завдання. Точнішою була б назва впорядкування (Шаблон:Lang-en), але через перевантаженість слова «порядок» (Шаблон:Lang-en) напрочуд різними значеннямиШаблон:Джерело ним не користуються.

Постановка задачі

Вхід алгоритму: послідовність з $n$ чисел $(a_1,a_2,\dots ,a_n)$

Вихід алгоритму: перестановка $(a_{\pi (1)},a_{\pi (2)},\dots a_{\pi (n)})$ вхідної послідовності таким чином, що $a_{\pi (1)}\le a_{\pi (2)}\le \dots \le a_{\pi (n)}$ ($\pi$ — перестановка послідовності чисел $1...n$).

Вхідна послідовність найчастіше представляється у вигляді n-елементного масиву, хоча може мати й інше представлення, наприклад, у вигляді зв'язного списку.

Вхідна послідовність: (5, 6, 1, 8, 5, 7, 4)

Вихідна послідовність: (1, 4, 5, 5, 6, 7, 8)

Структури даних

На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше кожен такий елемент є записом (Шаблон:Lang-en). У кожному записі є ключ (Шаблон:Lang-en), за яким, власне і здійснюється впорядкування; водночас є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом із ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого обсягу, то з метою звести до мінімуму переписування великих обсягів інформації, впорядкування відбувається не в самому масиві елементів, а в масиві вказівників на елементи.

Сам метод сортування не залежить від того, чи впорядковуються тільки числа, чи також і супутня інформація, тому при описі алгоритмів для простоти припускають, що елементи є числами.

Класифікація алгоритмів сортування

Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є:

• Час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є $O(n^2)$ — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час $O(n\log n)$. В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
• Необхідність додаткової пам'яті для сортування. Зазвичай необхідно O(1) пам'яті.
• Стабільність (Шаблон:Lang-en) — стабільне сортування не змінює взаємного розташування елементів з однаковими ключами.

Теорема про найкращий час сортування

Якщо алгоритм сортування у своїй роботі спирається тільки на операції порівняння двох об'єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за $O(n\log n)$ в найгіршому випадку.

Доведення

На кожному кроці алгоритм проводить одне порівняння, результатом якого є один з двох варіантів:

1. $A\le B$
2. $A>B$

Подальші дії алгоритм робитиме залежно від результату порівняння. Отже, всю роботу алгоритму можна представити у вигляді бінарного дерева, в листах якого лежать можливі перестановки вхідного масиву.

Отже, дерево має $n!$ листів, а висота дерева є $\log (n!)$. Час роботи в найгіршому випадку пропорційний висоті дерева:

$O(\log (n!))=O(\log \left(\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n\right))=O(n\log n)$.

Ці швидкі алгоритми використовуються в реальних задачах. Проте більшість із них нестабільні. Стабільні алгоритми, що працюють за час $O(n\log n)$, потребують $O(n)$ додаткової пам'яті.

Відомий стабільний алгоритм сортування, що не вимагає додаткової пам'яті, працює за час $O(n{\log }^{2}n)$.

Ще один клас алгоритмів використовує у своїй роботі деяку додаткову інформацію про елементи, що впорядковуються (наприклад, те що вони є різними числами в деякому діапазоні). Завдяки цьому вони працюють за час $O(n)$.

Відомі алгоритми сортування

За час $O(n^2)$:

• Сортування вибором — (Шаблон:Lang-en) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
• Сортування вставкою (включенням) — (Шаблон:Lang-en) — визначаємо місце, де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
• Сортування обміном (сортування бульбашкою, Шаблон:Lang-en) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
• Сортування методом бінарної вставки

За час $O(n\log n)$:

• Плавне сортування (Шаблон:Lang-en)
• Пірамідальне сортування
• Швидке сортування
• Сортування злиттям
• Timsort

За час $O(n)$ з використанням додаткової інформації про елементи:

• Сортування підрахунком
• Сортування за розрядами
• Сортування комірками

За час $O(n{\log }^{2}n)$:

• Сортування злиттям модифіковане
• Сортування Шелла

За час $O(nn!)$:

• Сортування перестановкою
• Випадкове сортування

Див. також

• Список алгоритмів.

Література

• Шаблон:TAOCP.v3
• Шаблон:CLRS

Посилання

• Алгоритм сортування Шаблон:Webarchive // ВУЕ
• Веблог «Штучний Інтелект», Обмінне сортування числових даних.
• А. Б. Ставровський, «Посібник з програмування для студентів 1 курсу факультету кібернетики» Шаблон:Webarchive,
• Розділ 17. Пошук, Сортування та Поняття Складності Шаблон:Webarchive