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

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

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

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

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

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

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

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

3.2.Метод простої вибірки.

Задано масив елементів R₁,R₂,…,R_n. Даний алгоритм реорганізує масив у висхідному порядку, тобто для його елементів буде мати місце співвідношення R_i < R_j - для всіх i,j=1..n_.

Алгоритм S.

S1. Цикл за індексом проходження. Повторювати кроки S2 - S 4 при i=1..n-1.

S2. Зафіксувати перший поточний елемент: встановити R0 = R_i.

S3. Пошук найменшого значення min R_j для елементів з індексом j=i+1, i+2,…,n

S4. Перестановка елементів. Якщо min R_j < R0 та j!=i, то min R_j <-> R0_.

S5. Кінець. Вихід.

З алгоритму S видно, що для сортування потрібно виконати n-1 проходження послідовності елементів. Одним проходженням називаємо пошук елементу з наступним найменшим значенням.

Проведемо невеликий аналіз алгоритму. При першому проходженні, коли знаходиться елемент з найменшим значенням, порівнюється п-1 елементів. У загальному випадку при i -му проходженні у процесі сортування порівнюється n-і елементів. Тоді загальна кількість порівнянь, які треба виконати для сортування масиву із n елементів буде:

Σ (n-i) = (n-1) + (n-2) +…+ (n-n+1) = 1/2n(n-1), i=1..n-1

Таким чином, ефективність алгоритму пропорційна величині n² (говорять, що алгоритм S має ефективність О( n² )).

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