Сортировка выбором
Ищет наименьшее из оставшихся значений и обменом ставит его на следующее место. Обменов очень мало, но число сравнений всегда одинаковое.
- Ω(n²)
- Θ(n²)
- O(n²)
- O(1)
- нет
- да
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- текущий минимум
- на окончательном месте
Попробуйте: Выберите обратный список. Сравнений будет ровно столько же, сколько для любого другого списка.
Как это работает
Просматриваем неотсортированную часть и находим наименьшее значение. Меняем его местами с первым неотсортированным, и ещё одно значение встаёт на своё окончательное место. Оставшиеся значения проверяются всегда все, даже если список уже отсортирован.
Когда стоит применять
Полезна, когда перемещать данные дорого, а читать дёшево: на каждую позицию приходится не больше одного обмена. В остальных случаях лучше взять сортировку вставками.