Сортировка выбором
Находим наименьшее значение в оставшейся части массива и меняем его местами с первым элементом этой части. Повторяем, пока все значения не займут окончательные позиции.
До 24 значений. Попробуйте повторы или отрицательные числа.
Шаг 0 / 24: Исходный массив. Ищем минимум в неотсортированной части.
Массив: [5, 2, 4, 2, 1]
Сравнения: 0 · Записи: 0
Зелёный — окончательный отсортированный префикс. Один подсвеченный столбец — текущий минимум, два — сравнение или обмен. Позиции считаются с нуля.
Что остаётся отсортированным
После каждого прохода префикс содержит наименьшие значения на окончательных местах. Следующий минимум ищем только в оставшейся части массива.
Почему сортировка нестабильна
Дальний обмен может изменить порядок равных значений. Попробуйте [2, 2, 1]: обмен первой двойки с единицей переместит её после второй двойки. Выбор первого минимума этого не предотвращает.
Сложность
- Сравнения (при любом порядке входа)
- n(n − 1) / 2
- Время: лучший, средний и худший случай
- Θ(n²)
- Обмены
- Не более max(0, n − 1)
- Дополнительная память самого алгоритма
- O(1)
Каждый проход просматривает всю оставшуюся часть, даже если массив уже отсортирован. Сравнения складываются в (n − 1) + (n − 2) + … + 1. Когда минимум уже на нужном месте, обмен пропускается: на отсортированном входе записей нет, но все сравнения остаются.
Сам алгоритм при сортировке на месте требует постоянной дополнительной памяти. Визуализатор хранит Θ(n²) снимков по n ячеек каждый: память истории составляет Θ(n³). Ввод ограничен 24 значениями.
Реализация на JavaScript
Обёртка копирует вход, чтобы сохранить исходный массив, поэтому вся функция дополнительно использует O(n) памяти. Цикл выполняет те же сравнения и обмены, что и демо.
function selectionSort(values) {
const result = [...values];
for (let start = 0; start < result.length - 1; start++) {
let minimum = start;
for (let i = start + 1; i < result.length; i++) {
if (result[i] < result[minimum]) minimum = i;
}
if (minimum !== start) {
[result[start], result[minimum]] = [result[minimum], result[start]];
}
}
return result;
}Сравнение трёх сортировок
| Алгоритм | Лучшее время | Худшее время | Стабильная | Изменения массива |
|---|---|---|---|---|
| Сортировка выбором | Θ(n²) | Θ(n²) | Нет | Не более n − 1 обменов |
| Сортировка вставками | Θ(n) | Θ(n²) | Да | Сдвиги: до Θ(n²) записей |
| Пузырьковая сортировка | Θ(n) | Θ(n²) | Да | Обмены соседей: до Θ(n²) записей |
Сортировка выбором делает мало обменов, но не ускоряется на уже отсортированном входе. Вставки удобны для небольших почти отсортированных массивов. Пузырьковая сортировка с ранним выходом тоже распознаёт отсортированный вход, но может делать много обменов соседей. У всех трёх квадратичное время в худшем случае.
Попробуйте [1, 2, 3, 4, 5] для сравнения счётчиков, [5, 4, 3, 2, 1] для обратного порядка и [2, 2, 1], чтобы проследить равные значения при дальнем обмене.
Видеоразбор
Работает на AlgiViz
Алгоритм сортировки выбором определён на этом сайте через операции AlgiViz. Каждое сравнение учитывается один раз, каждый обмен — как две записи в массив.