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

Задано масив елементів 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.