Сортировка выбором

Ищет наименьшее из оставшихся значений и обменом ставит его на следующее место. Обменов очень мало, но число сравнений всегда одинаковое.

• лучший Ω(n²)
• средний Θ(n²)
• худший O(n²)
• память O(1)
• нестабильное
• без дополнительной памяти

Что это значит?

• Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
• Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
• Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
• Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
• Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
• Без дополнительной памяти: сортирует внутри самого списка, без второго списка.