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

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

Рисунок 3 демонстрирует сортировочный процесс целиком. На каждом проходе выбирается наибольший из несортированных элементов и помещается на соответствующюю позицию. Первый проход разместит 93, второй - 77, третий - 55 и так далее. Функция показана в ActiveCode 3.

Для большей детализации CodeLens 3 позволит вам пройти весь алгоритм пошагово.

Вы можете видеть, что сортировка выбором совершает то же число сравнений, что и пузырьковая сортировка, поэтому является \(O(n^{2})\). Однако, из-за уменьшения количества перестановок, на тестовых заданиях она обычно выполняется быстрее. Фактически, для нашего списка пузырьковая сортировка сделает 20 перестановок, в то время как сортировка выбором - всего 8.