Задача сортування

Загальна задача сортування полягає в наступному:

нехай дано множину елементів, яка є індексованою, тобто довільно пронумерованою від 1 до n. Необхідно індексувати цю множину елементів так, щоб з умови i<j витікало a_i < а_j - для всіх i,j=1..n.

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

Будемо розглядати ефективність алгоритмів у термінах розмірності множини з точки зору простоти програмування. Задачу сортування зручніше розглядати в застосуванні до одновимірних масивів (векторів).

Нехай маємо вектор з n елементів R₁,R₂,…,R_n.. Задача сортування полягає у тому, щоб знайти таку перестановку елементів вектора, після якої вони розмістилися б у зростаючому порядку їх значень.

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

Наведемо основні алгоритми у формальному аспекті і розглянемо на прикладах їх роботу.