Сортування вибором. 
Порівняння загальних характеристик роботи різних методів сортування

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

Будемо будувати готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1)-му.

На i-му кроці вибираємо найменший з елементів a [i] … a [n] і міняємо його місцями з a [i]. Послідовність кроків при n = 5 зображена на Рис. 5.8.

Рисунок 2.8 — Приклад сортування вибором.

Незалежно від номера поточного кроку i, послідовність a [0] … a [i] (виділена курсивом) є впорядкованою. Таким чином, на (n-1)-му кроці вся послідовність, крім a [n] виявляється відсортованої, а a [n] стоїть на останньому місці по праву: все менші елементи вже пішли вліво.

Для знаходження найменшого елемента з n + 1, що розглядаються, алгоритм робить n порівнянь. З урахуванням того, що кількість розглянутих на черговому кроці елементів зменшується на одиницю, загальна кількість операцій обчислюється за формулою (2.1):

(2.1).

Таким чином, так як число обмінів завжди буде менше числа порівнянь, час сортування зростає квадратично щодо кількості елементів.

Алгоритм не використовує додаткової пам’яті: всі операції відбуваються «на місці» .

Розглянемо послідовність з трьох елементів, кожен з яких має два поля, а сортування йде за першою з них (Рис. 2.9).

Рисунок 2.9 — Сортування масивів з двома полями.

Результат її сортування можна побачити вже після кроку 0, так як більше обмінів не буде. Порядок ключів 2a, 2b був змінений на 2b, 2a, так що метод нестійкий.

Якщо вхідні послідовність майже впорядкована, то порівнянь буде стільки ж, значить алгоритм поводиться неприродно.