Короткі теоретичні відомості. Алгоритм, алгорифм (латинізоване «Algorithmi», від імені узбецького математика IX століття аль-Хорезмі) — система правил виконання обчислювального процесу

Алгоритм, алгорифм (латинізоване «Algorithmi», від імені узбецького математика IX століття аль-Хорезмі) — система правил виконання обчислювального процесу, що обов’язково приводить до розв’язання певного класу задач після скінченного числа операцій. При написанні комп’ютерних програм алгоритм описує логічну послідовність операцій. Поняття алгоритму належить до первісних понять математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел тощо) відомі людству з глибокої давнини. Проте в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.

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

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

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

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

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

Стабільним (англійською «Stable») називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем.

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

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

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

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

1. A ≤ B.

2. A > B.

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

Отже, дерево має n! листів, значить висота дерева дорівнює log(n!). Час роботи в найгіршому випадку пропорційний висоті дерева: O (log(n!)) = O (log((2 πn)^½∙(n / e) ⁿ)) = O (n ∙log(n)).

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

Відомий стабільний алгоритм сортування, що не вимагає додаткової пам’яті працює за час O (n ∙log² n).

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