Сортировка выбором
Сортировка выбором упорядочивает список так, как многие раскладывают карты в руке: найти наименьшую карту, положить её первой, затем найти наименьшую из остальных. Она делает много сравнений, но очень мало обменов, а время её работы почти не зависит от порядка списка.
Идея
Разделите список на отсортированную часть слева, сначала пустую, и неотсортированную часть справа. Просмотрите неотсортированную часть и запомните, где стоит её наименьшее значение. Поменяйте это значение местами с первым неотсортированным: отсортированная часть выросла на одно значение. Повторяйте, пока не останется одно значение — оно обязательно наибольшее.
Пример
Возьмём 5, 1, 4, 2, 8. Первый проход просматривает все пять значений, находит наименьшее — 1 — и меняет его местами с 5: 1, 5, 4, 2, 8. Второй проход просматривает 5, 4, 2, 8, находит 2 и меняет его местами с 5: 1, 2, 4, 5, 8. Третий проход находит 4 уже на месте, четвёртый — 5 уже на месте, поэтому ничего не двигается. Итого 4 + 3 + 2 + 1 = 10 сравнений и всего 2 обмена. Сортировке пузырьком на том же списке нужно 4 обмена.
Всегда одно и то же число сравнений
Чтобы точно знать, какое значение наименьшее, нужно просмотреть все оставшиеся. Проход 1 делает n − 1 сравнений, проход 2 — n − 2, и так далее до 1, а в сумме это n(n − 1)/2. Это число не зависит от списка: отсортированный список требует ровно столько же сравнений, сколько обратный. У сортировки выбором нет ранней остановки, ведь проход, который нашёл наименьшее значение уже в начале, ничего не узнал об остальных.
Мало обменов
Каждый проход делает не больше одного обмена, поэтому сортировка выбором никогда не делает больше n − 1 обменов и пропускает обмен, если наименьшее значение уже на месте. Сортировка пузырьком и сортировка вставками делают столько обменов, сколько в списке пар в неправильном порядке, а это может быть около n²/2. Когда записать значение намного дороже, чем прочитать два, например в памяти, которая изнашивается от каждой записи, малое число обменов — преимущество.
Неустойчивость
Сортировка устойчива, если равные значения сохраняют исходный порядок. Сортировка выбором неустойчива, потому что обмен на большое расстояние может перенести значение через равное ему. В 2, 2, 1 первый проход меняет местами первую двойку и единицу, и получается 1, 2, 2, где две двойки стоят уже в обратном порядке. Вариант, который сдвигает промежуточные значения вместо обмена, устойчив, но перемещает гораздо больше значений.
Попробуйте сами
Откройте приложение и нажмите «Пуск» или «Шаг», чтобы идти по одному сравнению. Просматриваемое значение выделено, у текущего минимума свой цвет, а каждый проход заканчивается обменом в отсортированную часть слева. Попробуйте отсортированный и обратный список: сравнений получится одинаково, отличаются только обмены.
Часто задаваемые вопросы
Какова временная сложность сортировки выбором?
O(n²) в любом случае: ровно n(n − 1)/2 сравнений для n значений при любом их порядке. Она делает не больше n − 1 обменов и требует всего O(1) дополнительной памяти.
Чем сортировка выбором отличается от сортировки пузырьком?
Сортировка пузырьком меняет местами соседей по ходу и может остановиться раньше, если за проход не было обменов. Сортировка выбором только запоминает, где стоит наименьшее значение, и делает один обмен в конце каждого прохода. Сортировка выбором делает меньше обменов, а сортировка пузырьком быстрее на почти отсортированных списках.
Устойчива ли сортировка выбором?
Нет. Обмен может перенести значение через другое, равное ему, поэтому равные значения могут поменяться порядком. Её можно сделать устойчивой, сдвигая значения вместо обменов, но это требует больше перемещений.
Как пирамидальная сортировка связана с сортировкой выбором?
Пирамидальная сортировка — это сортировка выбором с более быстрым способом найти следующее значение: она хранит неотсортированную часть в куче, поэтому каждый выбор занимает около log n шагов вместо полного просмотра. Это снижает общее время до O(n log n).
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать сортировку выбором