Перегляд вихідного коду сторінки Алгоритм сортування

'''Алгоритм сортування'''&nbsp;— це [[алгоритм]], що розв'язує задачу [[сортування]], тобто здійснює впорядкування лінійного [[Зв'язаний список|списку]] ([[Масив (структура даних)|масиву]]) елементів.

== Термінологія ==
Термін '''сортування''' ({{lang-en|sorting}}) означає розділення елементів за певними ознаками (сортами) і не дуже точно описує поставлене завдання. Точнішою була б назва '''впорядкування''' ({{lang-en|ordering}}), але через перевантаженість слова «порядок» ({{lang-en|order}}) напрочуд різними значеннями{{джерело|дата=червень 2022}} ним не користуються.

== Постановка задачі ==
'''Вхід алгоритму:''' послідовність з <math>n</math> чисел <math>(a_1, a_2, \dots\;,a_n)</math>

'''Вихід алгоритму:''' [[перестановка]] <math>(a_{\pi\;(1)},a_{\pi\;(2)},\dots\;a_{\pi\;(n)})</math> вхідної послідовності таким чином, що <math>a_{\pi\;(1)}\le\;a_{\pi\;(2)}\le\dots\le\;a_{\pi\;(n)}</math> (<math>\pi\;</math>&nbsp;— перестановка послідовності чисел <math>1...n</math>).

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

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

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

== Структури даних ==
{{main|Структура даних}}

На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше кожен такий елемент є [[Структура (тип даних)|записом]] ({{lang-en|record}}). У кожному записі є ключ ({{lang-en|key}}), за яким, власне і здійснюється впорядкування; водночас є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом із ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого обсягу, то з метою звести до мінімуму переписування великих обсягів інформації, впорядкування відбувається не в самому масиві елементів, а в масиві [[вказівник]]ів на елементи.

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

== Класифікація алгоритмів сортування ==
Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є:
* Час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є <math>\;O(n^2)</math>&nbsp;— це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час <math>O(n\log\;n)</math>. В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
* Необхідність додаткової пам'яті для сортування. Зазвичай необхідно '''''O(1)''''' пам'яті.
* '''Стабільність''' ({{lang-en|Stability}})&nbsp;— [[стабільне сортування]] не змінює взаємного розташування елементів з однаковими ключами.

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

=== Доведення ===
На кожному кроці алгоритм проводить одне порівняння, результатом якого є один з двох варіантів:
# <math>A\le\;B</math>
# <math>\;A>B</math>

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

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

<math>O(\log(n!)) = O\left(\log\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)\right) = O(n\log\;n)</math>.

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

Відомий стабільний алгоритм сортування, що [[Алгоритм з виконанням на місці|не вимагає додаткової пам'яті]], працює за час <math>O(n\log^2\;n)</math>.

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

== Відомі алгоритми сортування ==
За час <math>\;O(n^2)</math>:
* [[Сортування вибором]]&nbsp;— ({{lang-en|Selection sort}})&nbsp;— пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
* [[Сортування вставкою]] (включенням)&nbsp;— ({{lang-en|Insertion sort}})&nbsp;— визначаємо місце, де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
* [[Сортування обміном]] (сортування бульбашкою, {{lang-en|Bubble sort}})&nbsp;— для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
* Сортування методом бінарної вставки

За час <math>O(n\log\;n)</math>:
* [[Плавне сортування]]&nbsp;({{lang-en|Smoothsort}})
* [[Пірамідальне сортування]]
* [[Швидке сортування]]
* [[Сортування злиттям]]
* [[Timsort]]

За час <math>\;O(n)</math> з використанням додаткової інформації про елементи:
* [[Сортування підрахунком]]
* [[Сортування за розрядами]]
* [[Сортування комірками]]

За час <math>O(n\log^2\;n)</math>:
* [[Сортування злиттям модифіковане]]
* [[Сортування Шелла]]
За час <math>O(nn!)</math>:
* [[Сортування перестановкою]]
* [[Випадкове сортування]]

== Див. також ==
{{wikisource|Категорія:Реалізації алгоритмів сортування|Приклади реалізації алгоритмів сортування}}
* [[Список алгоритмів]].

== Література ==
* {{TAOCP.v3}}
* {{CLRS|chapter=Section II. Сортування і порядкові статистики}}

== Посилання ==
* [https://vue.gov.ua/Алгоритм_сортування Алгоритм сортування] {{Webarchive|url=https://web.archive.org/web/20220225084452/https://vue.gov.ua/Алгоритм_сортування |date=25 лютого 2022 }} // [[ВУЕ]]
* Веблог «Штучний Інтелект», [https://web.archive.org/web/20070601160908/http://ai-blog.org/node/ExchangeSort Обмінне сортування числових даних].
* А.&nbsp;Б.&nbsp;Ставровський, [http://www.unicyb.kiev.ua/Library/PROG/Zmist.htm «Посібник з програмування для студентів 1 курсу факультету кібернетики»] {{Webarchive|url=https://web.archive.org/web/20070716185819/http://www.unicyb.kiev.ua/Library/PROG/Zmist.htm |date=16 липня 2007 }},
* ''[http://www.unicyb.kiev.ua/Library/PROG/abut7.htm Розділ 17. Пошук, Сортування та Поняття Складності] {{Webarchive|url=https://web.archive.org/web/20070317064828/http://www.unicyb.kiev.ua/Library/PROG/abut7.htm |date=17 березня 2007 }}''

{{Algorithm-stub}}

{{Алгоритми сортування}}
{{ВП-портали|Програмування|}}

[[Категорія:Алгоритми сортування| ]]