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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Постановка задачі[ред.ред. код]

Вхід алгоритму: послідовність з 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)

Структури даних[ред.ред. код]

Докладніше: Структура даних

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

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

Характеристики алгоритмів[ред.ред. код]

Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є: час необхідний на впорядкування n-елементного масиву і додаткова пам'ять необхідна для впорядкування. Крім цих двох характеристик, сортування буває стабільним чи нестабільним, з використанням додаткової інформації про елементи, чи без використання.

Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є \;O(n^2), це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.

Інший клас алгоритмів здійснює впорядкування за час O(n\log\;n). В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.

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

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

Доведення[ред.ред. код]

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

  1. A\le\;B
  2. \;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)

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

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

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

За час O(nn!)

Походження терміну[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Джерела інформації[ред.ред. код]

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