Информатика · объяснение и практика

Сортировка выбором: какой минимум фиксируется после прохода

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Поиск и сортировка · Учебная карта

Главная мысль

В сортировке выбором на шаге 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А]. Равные тройки поменяли взаимный порядок, хотя итоговые числа упорядочены правильно. Значит, обычная схема с дальним обменом не является стабильной. Это свойство нельзя проверить списком, в котором все ключи различны: тогда перестановка равных элементов просто не возникает.

Сортировка вставками выполняет другую работу: размещает очередной элемент внутри готового префикса сдвигами. Сортировка выбором каждый раз ищет минимум всей оставшейся части. У обеих есть готовая левая часть, но её смысл и изменение различаются. Для пустого списка и одного элемента сравнений не нужно. Для длинного уже упорядоченного списка описанный выбор всё равно тратит квадратичное число сравнений: удачный исходный порядок не сокращает полный просмотр хвоста.

От чтения к действию

А теперь — вы

В списке [5, 8, 1, 4] выполнен ровно один проход описанной сортировки выбором по возрастанию. Какой список получится после обмена найденного минимума с началом?

Частые вопросы

После одного прохода весь хвост должен быть отсортирован?

Нет. Зафиксирован следующий минимум, а остаток сохраняет произвольный порядок до последующих проходов.

Почему минимум ищут до конца, а не до первого меньшего элемента?

Первый меньший элемент ещё не обязательно минимален. Нужное утверждение получается только после просмотра всей оставшейся части.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться