Selection Sort

Проблема

Нужно отсортировать массив, но при этом минимизировать количество операций записи (перестановок), потому что запись в память или на диск иногда дороже, чем чтение и сравнение. Пузырьковая сортировка делает перестановку почти при каждом сравнении - хочется алгоритм, который переставляет элементы реже.

Решение

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

Как это работает

Представь массив [64, 25, 12, 22, 11]. Сортировка выбором делит его мысленно на отсортированную часть слева и неотсортированную справа. На первом шаге граница стоит у самого начала - весь массив неотсортирован. Алгоритм просматривает все 5 элементов, находит минимум 11 и меняет его с первым элементом: [11, 25, 12, 22, 64]. Граница сдвигается вправо - 11 навсегда занял своё место.

Почему сортировка выбором всегда делает ровно n(n-1)/2 сравнений? На первом шаге внутренний цикл просматривает n-1 элементов, на втором - n-2, и так далее. Сумма (n-1) + (n-2) + ... + 1 = n(n-1)/2. При n=8 это 28 сравнений - ровно столько же, отсортирован ли массив или перевёрнут. Внутренний цикл не умеет «срезать угол»: он должен пройти до конца неотсортированной части, чтобы гарантировать нахождение истинного минимума.

Зато число перестановок под жёстким контролем: не более n-1 за всё время. На каждом из n-1 шагов происходит не более одного обмена - минимум меняется местами с элементом на границе. Если минимум уже стоит на границе, обмен пропускается (if (minIndex !== i)). Для n=8 это максимум 7 перестановок против потенциальных 28 у пузырьковой - именно это делает алгоритм ценным там, где запись в память дороже чтения.

Инвариант цикла - ключ к корректности алгоритма. В начале каждого шага i все элементы с индексами 0..i-1 уже стоят на своих финальных позициях и больше никогда не трогаются. После шага i элемент с индексом i добавляется к этой «заморозке». Именно поэтому достаточно n-1 шагов: после n-1 итераций левее границы стоят n-1 наименьших элементов, а оставшийся единственный обязан быть наибольшим.

Почему сортировка выбором неустойчива (unstable)? Возьмём [3a, 3b, 1], где 3a и 3b - одинаковые значения, исходный порядок: a левее b. На первом шаге минимум 1 стоит в позиции 2 и меняется с позицией 0: результат [1, 3b, 3a]. Теперь 3b левее 3a - исходный порядок нарушен. Прямой обмен через прыжок - корень нестабильности: минимум телепортируется на нужное место, перепрыгивая через равный ему элемент без его сдвига.

Сравнение с пузырьковой раскрывает главный компромисс. Оба алгоритма делают O(n²) сравнений в среднем и худшем случае. Но в числе записей разрыв огромный: пузырьковая переставляет элементы почти при каждом сравнении - до O(n²) перестановок. Сортировка выбором ограничивает себя до n-1 перестановок ценой потери раннего выхода. Пузырьковая с флагом завершается за O(n) на уже отсортированных данных - сортировка выбором всегда тратит все n(n-1)/2 сравнений, даже если массив идеально отсортирован.

Как сделать сортировку выбором устойчивой - ценой дополнительных записей? Вместо прямого обмена найденного минимума с границей нужно сдвинуть все элементы между границей и минимумом на одну позицию вправо (как в сортировке вставками) и вставить минимум на место границы. Это сохраняет порядок равных элементов, но превращает одну перестановку за шаг в до O(n) сдвигов за шаг. Итоговое число записей приближается к O(n²) - столько же, сколько у пузырьковой, но уже без её раннего выхода.

Нюансы выбора

Главная ниша сортировки выбором - носители с дорогой записью. Flash-память (NAND, NOR) и EEPROM имеют ограниченное число циклов перезаписи - обычно 100 000 - 1 000 000 для одной ячейки. Каждая лишняя операция записи приближает конец жизни носителя. В этом контексте n-1 перестановок против O(n²) у пузырьковой - принципиальная разница: при n=100 это 99 перестановок против потенциальных 4950.

Маленькие массивы (n < 10-15) - ещё одна подходящая ниша. При n < 10 разница между O(n²) и O(n log n) незаметна на фоне константных расходов и оверхеда вызовов. Предсказуемость алгоритма (всегда ровно n(n-1)/2 итераций внутреннего цикла) даже удобна: поведение детерминировано и легко отлаживается. Однако при n < 10 сортировка вставками обычно быстрее на практике - она делает меньше физических записей на почти упорядоченных данных.

Сортировка выбором подходит, когда устойчивость не нужна. Если ключ сортировки - единственное поле объекта, или порядок среди равных элементов заведомо не важен, отсутствие гарантии стабильности не создаёт проблем. Как только появляется требование «при равных значениях сохранить исходный порядок» - нужны Timsort, merge sort или сортировка вставками, все из которых устойчивы по определению.

Три оси выбора, если сводить итог по соседним алгоритмам (компромисс сравнений и перестановок разобран в разделе «Как это работает»): перестановки, сравнения, устойчивость. Практический вывод - брать сортировку выбором стоит только тогда, когда минимизация записи явно важнее и скорости на почти готовых данных, и сохранения порядка одинаковых элементов.

Никогда для больших данных. При n > 50-100 даже простой quicksort опережает сортировку выбором настолько, что экономия на перестановках полностью съедается разницей в сравнениях. Merge sort даёт O(n log n) гарантированно и устойчиво ценой O(n) памяти. На современных CPU кэш-промахи от n(n-1)/2 квазислучайных чтений при поиске минимума стоят дороже, чем может сэкономить алгоритм на перестановках.

Нужен алгоритм с той же идеей «извлеки минимум, поставь на место», но без O(n²)? Тогда искать нужно не замену сортировке выбором, а её ускоренную версию - Heapsort, разобранную в разделе «Примеры в коде». Сама сортировка выбором в этом случае не применяется - она лишь подсказывает, в какую сторону думать.

Примеры в коде

Встроенные системы - одна из реальных ниш алгоритма. Типичный пример - медианный фильтр на микроконтроллере: собери 7-9 последних показаний АЦП (датчик температуры, давления), отсортируй, возьми средний элемент. При n=7 алгоритм делает 21 сравнение и не более 6 перестановок. На ARM Cortex-M0 с flash на 100k циклов это принципиально: лишние записи укорачивают жизнь прошивки на реальных проектах - STM32, Arduino, ESP32.

Самое влиятельное «потомство» сортировки выбором - Heapsort (пирамидальная сортировка). Идея та же: извлечь минимум, положить на финальное место, сдвинуть границу. Разница - в инструменте поиска минимума: Heapsort держит неотсортированную часть в виде двоичной кучи и извлекает экстремальный элемент за O(log n) вместо линейного O(n). Итог - O(n log n) при O(1) памяти. std::partial_sort в GCC использует heap-based подход, унаследованный из этой идеи.

Ранние движки JavaScript использовали сортировку выбором для коротких массивов. V8 (Chrome) до 2019 года переключался на insertion sort для массивов длиной < 10 элементов; ещё более ранние версии содержали selection sort как запасной вариант для крошечных массивов. После 2019 года V8 полностью перешёл на Timsort, устранив все O(n²) случаи. SpiderMonkey (Firefox) аналогично эволюционировал от ad-hoc сортировок для малых массивов к унифицированному Timsort.

Stable selection sort (сдвиг вместо обмена - механика разобрана в разделе «Как это работает») встречается в учебных курсах по алгоритмам как классическое упражнение «почему устойчивость стоит записей», например в задачах CLRS и на GeeksforGeeks. В продакшене этот вариант не прижился нигде: там, где нужна устойчивость, стандартные библиотеки (Python, Java, C++) используют Timsort, а не stable selection sort.

Соревновательное программирование (Codeforces, LeetCode) - ещё одна ниша для этого алгоритма: задача «минимальное число перестановок для сортировки» напрямую моделирует его работу. Число инверсий в массиве указывает, сколько перестановок нужно. Это же свойство - гарантированно ограниченное число обменов - используют в задачах, где стоимость перестановки задана явно и нужно минимизировать суммарные расходы.

Где сортировка выбором не встречается? В стандартных библиотеках языков общего назначения - нигде. Python (list.sort) - Timsort. Java (Arrays.sort для объектов) - Timsort. C++ (std::sort) - introsort. Go (sort.Slice) - pdqsort. Rust (slice::sort_unstable) - pdqsort. Единственное конкурентное преимущество алгоритма (минимальные записи) доступно через Heapsort при O(n log n) сравнениях - это и объясняет его отсутствие в современных стандартных библиотеках.

Когда применять

• Когда операция записи в память заметно дороже сравнения - например, запись на флеш-память с ограниченным числом циклов перезаписи.
• Для небольших массивов или как шаг в комбинированных алгоритмах (например, в качестве finishing touch для маленьких подмассивов в интроспективной сортировке).

Примеры из практики

• Сортировка данных на носителях с дорогой записью - там, где важно свести число операций записи к минимуму, а не число сравнений.
• Учебные визуализации - предсказуемое, линейно нарастающее поведение делает алгоритм удобным для демонстрации самой идеи «выбора минимума».