Информатика · объяснение и практика
Сортировка выбором: какой минимум фиксируется после прохода
Прослеживаем сортировку выбором: ищем минимум во всей оставшейся части, фиксируем следующий элемент и отличаем обмен от сдвигов сортировки вставками.

В теме Поиск и сортировка · Учебная карта
Главная мысль
В сортировке выбором на шаге i находят минимальный элемент среди позиций от i до конца и меняют его с элементом на позиции i. После шага слева находятся уже выбранные наименьшие элементы в окончательном порядке. В обычной реализации число сравнений ключей равно n(n−1)/2 независимо от исходной упорядоченности списка; обмены выполняются отдельно от сравнений.
Готовая часть содержит именно самые маленькие элементы
Пусть слева уже размещены несколько элементов. Они не просто стоят по возрастанию: каждый из них не больше любого ещё не выбранного элемента справа. Поэтому будущие шаги не должны менять готовую левую часть. Чтобы добавить следующий элемент, просматривают всю оставшуюся часть и запоминают позицию её минимума. Одного сравнения с соседом недостаточно, поскольку ещё меньший ключ может находиться ближе к концу списка.
Перед просмотром можно принять за текущий минимум первый элемент неготовой части. Затем каждый следующий сравнивают с ним и при строгом уменьшении обновляют запомненную позицию. Пока просмотр не завершён, найденный минимум относится только к уже просмотренному отрезку. Финальный обмен делают после просмотра. Если менять элементы при каждом новом рекорде, получится иной вариант алгоритма с другим числом обменов; эту процедуру нельзя незаметно считать тем же шагом.
Отделяем поиск позиции от перестановки
Рассмотрим список [7, 2, 5, 1]. В первом проходе минимум всей четвёрки равен единице и находится в последней позиции. Обмен с началом даёт [1, 2, 5, 7]. Во втором проходе достаточно сравнить двойку с пятёркой и семёркой: она уже на нужном месте. В третьем сравнивают пятёрку с семёркой. Список оказался отсортирован уже после первого обмена, но обычная реализация всё равно выполняет оставшиеся просмотры.
Сравнения ключей по проходам составляют три, два и одно, всего шесть. Для последней единственной позиции искать среди других элементов уже нечего. Обмен элемента с самим собой может присутствовать в коде или пропускаться; это меняет счёт вызовов обмена, но не число сравнений в описанной схеме. Поэтому вопрос о трудоёмкости должен называть, что именно считается: сравнения, действительные перестановки разных позиций или все операции программы.
Пример
В [9, 4, 6, 2, 8] выполните один проход сортировки выбором по возрастанию с обменом только после полного поиска минимума.
Минимум 2 стоит на позиции 3 при нумерации с нуля. После обмена позиций 0 и 3 получим [2, 4, 6, 9, 8]. Готова только первая позиция; хвост не обязан быть отсортирован. Для нахождения минимума потребовались четыре сравнения.
Почему обмен может нарушить порядок равных ключей
Возьмём помеченные элементы [3А, 3Б, 1] и сравнивай только числовую часть. Обмен первого элемента с единицей даст [1, 3Б, 3А]. Равные тройки поменяли взаимный порядок, хотя итоговые числа упорядочены правильно. Значит, обычная схема с дальним обменом не является стабильной. Это свойство нельзя проверить списком, в котором все ключи различны: тогда перестановка равных элементов просто не возникает.
Сортировка вставками выполняет другую работу: размещает очередной элемент внутри готового префикса сдвигами. Сортировка выбором каждый раз ищет минимум всей оставшейся части. У обеих есть готовая левая часть, но её смысл и изменение различаются. Для пустого списка и одного элемента сравнений не нужно. Для длинного уже упорядоченного списка описанный выбор всё равно тратит квадратичное число сравнений: удачный исходный порядок не сокращает полный просмотр хвоста.
От чтения к действию
А теперь — вы
Частые вопросы
После одного прохода весь хвост должен быть отсортирован?
Нет. Зафиксирован следующий минимум, а остаток сохраняет произвольный порядок до последующих проходов.
Почему минимум ищут до конца, а не до первого меньшего элемента?
Первый меньший элемент ещё не обязательно минимален. Нужное утверждение получается только после просмотра всей оставшейся части.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
Открыть темуЧто сохраняет стабильная сортировка одинаковых ключей
Что означает стабильность сортировки, какой порядок сохраняется при равных ключах и как различаются sorted и изменение списка на месте в Python.
Открыть тему