Сортировка выбором. 
Теоретические основы информатики

Алгоритм сортировки выбором (англ, selection sort) является достаточно простым для понимания и реализации. В случае небольшого количества элементов он дает приемлемые результаты по времени. Пусть исходное множество элементов А = = {cii, а-2,…, а_п} несортированно.

На первом этапе сортировки выбором определяется минимальный элемент этого множества и меняется местами с первым элементом. После этого элемент а находится на своем месте (отсортирован), а подмножество {аг,…, а"} можно считать несортированным. Затем процедура поиска минимального элемента повторяется для этого подмножества., он меняется местами с элементом «2- После этого подмножество {ai, a₂} является отсортированым, а подмножество {аз,… а_п } можно считать несортированным. Процесс продолжается дальше и завершается, когда упорядоченным подмножеством окажется {aj,…, a"_i}. Элемент а_п при этом будет автоматически находиться на своем месте (это максимальный элемент).

Пример 11.2. Используя алгоритм сортировки выбором, упорядочить множество чисел А = {9,3,12,1,8,5} по возрастанию.

Решение. Будем обозначать последовательные состояния сортируемого множества А как ?0,51,52,… (⁵° ^— начальное состояние до применения алгоритма сортировки). В первом столбце табл. 11.1 указаны состояния множества сортируемых элементов, во втором — действия, выполняемые после перехода в это состояние.

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

Таблица 11.1

Для состояний Si и 54 минимальные элементы среди несортированных уже стоят на своих местах, поэтому фактически менять местами элементы не нужно, но для общности изложения переходы из этих состояний в последующие указаны в таблице. Процесс останавливается после того, как отсортированным оказывается предпоследний элемент. ?

Оценим количество сравнений Т (п). При первом просмотре Т (1) = п — 1, при втором — Т (2) = п — 2, при последнем — 1. Общее количество.

(сумма элементов арифметической прогрессии) или Т (га) = О (га²). Это означает, что с ростом значения п количество сравнений будет расти как квадратичная функция от га, т. е. алгоритм сортировки выбором имеет сложность порядка О (га²).

Рассмотренный алгоритм имеет альтернативные названия: линейная сортировка, сортировка простым выбором, сортировка отбором.