Сортировка выбором

Идея

Находим наименьший элемент и ставим его первым. Затем находим наименьший среди оставшихся и ставим вторым. Повторяем, пока весь массив не встанет по порядку. Массив делится на отсортированное начало и неотсортированный хвост; каждый шаг переносит один элемент из хвоста в конец начала.

Пример

Сортируем [5, 2, 4, 6, 1, 3]. Отсортированное начало выделено жирным.

Шаг	Минимум остатка	Массив после шага
1	1 → обмен с 5	1, 2, 4, 6, 5, 3
2	2 → уже на месте	1, 2, 4, 6, 5, 3
3	3 → обмен с 4	1, 2, 3, 6, 5, 4
4	4 → обмен с 6	1, 2, 3, 4, 5, 6
5	5 → уже на месте	1, 2, 3, 4, 5, 6

15 сравнений и всего 3 обмена.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

SELECTION-SORT(A)
  for i = 0 to n − 2
    min = i
    for j = i + 1 to n − 1
      if A[j] < A[min]
        min = j
    if min ≠ i
      swap A[i] and A[min]

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n²)	O(n²)	O(n²)	O(1)	нет	да

• Всегда ровно $\frac{n(n-1)}{2}$ сравнений: чтобы найти минимум, нужно посмотреть на каждый оставшийся элемент, какими бы ни были данные.
• Не больше n − 1 обменов — меньше, чем у любого другого алгоритма здесь. Полезно, когда запись намного дороже чтения (например, во флеш-памяти).
• Неустойчивая: дальний обмен может перепрыгнуть через равный элемент. В [2a, 2b, 1] первый шаг меняет 2a и 1, получается [1, 2b, 2a].

Когда применять

Когда число записей важнее числа сравнений, или как учебный пример инварианта «отсортированное начало + неотсортированный хвост».

Использование

import { selectionSort } from 'ts-ds';

const array = [5, 2, 4, 6, 1, 3];
selectionSort(array);

Справочник API

Литература

• Кнут, Искусство программирования, т. 3, §5.2.3 «Сортировка посредством выбора».
• Седжвик, Алгоритмы, §2.1.