Задание № 24 · ЕГЭ

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

Алгоритм сортировки последовательным выбором минимального или максимального элемента

2 мин чтенияСложность: Обновлено 29 сентября 2026

Сортировка выбором — это алгоритм, который по очереди находит минимальный элемент в неотсортированной части массива и ставит его на очередную позицию. Так постепенно строится отсортированная последовательность слева направо.

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

Алгоритм сортировки, при котором на каждом шаге из неотсортированной части последовательности выбирают минимальный элемент и меняют его местами с первым элементом этой части. Для сортировки по убыванию выбирают максимальный элемент.

Как работает алгоритм

Пусть дан массив из \(n\) элементов. На первом шаге ищут минимум во всём массиве и меняют его с элементом на позиции \(0\). На втором шаге ищут минимум среди элементов с позиций \(1\) до \(n-1\) и ставят его на позицию \(1\). Затем область поиска каждый раз сдвигается вправо. Для поиска минимума используют приём, описанный на странице поиска минимума и максимума.

\[i=0,1,\ldots,n-2;\qquad j=\operatorname*{arg\,min}_{k=i,\ldots,n-1} a_k\]

После нахождения индекса \(j\) выполняют обмен \(a_i\) и \(a_j\). После \(n-1\) шагов массив отсортирован. Последний элемент уже оказывается на своём месте автоматически.

№

Пример

Массив \([5, 2, 4, 1]\). Первый минимум — \(1\): обмен с \(5\) даёт \([1, 2, 4, 5]\). На следующем шаге минимум среди \([2,4,5]\) — это \(2\), обмен не нужен. Затем выбирают \(4\). Результат: \([1,2,4,5]\).

Не путайте с пузырьковой сортировкой

В сортировке выбором сначала находят один нужный элемент во всей неотсортированной части и выполняют обычно один обмен. В пузырьковой сортировке соседние элементы многократно сравниваются и обмениваются; выбранный минимум не ищут отдельным проходом.

Свойства

Время работы — \(O(n^2)\) сравнений в лучшем, среднем и худшем случаях.
Дополнительная память — \(O(1)\): элементы переставляются внутри исходного массива.
Алгоритм выполняет не более \(n-1\) обменов, поэтому удобен, когда обмены дороже сравнений.

Проверьте понимание

Какой элемент выбирают на третьем шаге сортировки выбором по возрастанию?

Главное за минуту

Главное

Сортировка выбором последовательно выбирает минимум или максимум из неотсортированной части.
При сортировке по возрастанию на шаге \(i\) минимум ставят на позицию \(i\).
Сложность алгоритма — \(O(n^2)\), дополнительная память — \(O(1)\).