Алгоритми сортування - Вікіпедія

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

### Матеріал з Вікіпедії — вільної енциклопедії.

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

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

Вхід алгоритму: послідовність з n чисел

Вихід алгоритму: перестановка вхідної послідовності таким чином, що ( — перестановка послідовності чисел 1...n).

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

Приклад

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Відомий стабільний алгоритм сортування, що не вимагає додаткової пам'яті працює за час

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

## [ред.] Відомі алгоритми сортування

За час

- сортування вибором
- сортування вставкою
- сортування обміном

За час

- сортування купою
- швидке сортування
- сортування злиттям

За час з використанням додаткової інформації про елементи

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

За час

- сортування злиттям модифіковане

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

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

Отримано від "http://uk.wikipedia.org../../../%D0%B0/%D0%BB/%D0%B3/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F.html"

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

##### Views

- Стаття
- Обговорення
- Поточна версія

##### Пошук

##### Іншими мовами

- العربية
- Català
- Česky
- Deutsch
- English
- Español
- فارسی
- Suomi
- Français
- עברית
- Íslenska
- Italiano
- Lietuvių
- Nederlands
- Polski
- Português
- Русский
- Svenska
- ไทย