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

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

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

Термін сортування (англ. sorting) означає розділення елементів за певними ознаками (сортами) і не дуже точно описує поставлене завдання. Точнішою була б назва впорядкування (англ. ordering), але через перевантаженість слова «порядок» (англ. order) напрочуд різними значеннями, в цьому випадку ми ним не скористалися.

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

Вхід алгоритму: послідовність з $n$ чисел $(a_{1},a_{2},\dots \;,a_{n})$

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

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

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

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

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

На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше, кожен такий елемент є записом (англ. record). В кожному записі є ключ (англ. key), по якому власне і здійснюється впорядкування, в той же час є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом з ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого обсягу, то з метою звести до мінімуму переписування великих обсягів інформації, впорядкування відбувається не у самому масиві елементів, а в масиві вказівників на елементи.

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

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

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

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

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

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

Доведення

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

$A\leq \;B$
$\;A>B$

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

Отже, дерево має $n!$ листів, а висота дерева є $\log(n!)$ . Час роботи в найгіршому випадку пропорційний висоті дерева: $O(\log(n!))=O\left(\log \left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\right)\right)=O(n\log \;n)$

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

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

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

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

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

Сортування вибором — (англ. Selection sort) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
Сортування вставкою — (англ. Insertion sort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
Сортування обміном (сортування бульбашкою, англ. Bubble sort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
Сортування методом бінарної вставки

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

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

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

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

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

Література

Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1.

Див. також

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

Посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.