Сортировка выбором
В каждой зоне находим минимум и ставим его в начало зоны — обменов меньше, чем у пузырька.
1function selectionSort(a: number[]): number[] {2 for (let start = 0; start < a.length - 1; start++) {3 let min = start4 for (let i = start + 1; i < a.length; i++) {5 if (a[i] < a[min]) min = i6 }7 const t = a[min]8 a[min] = a[start]9 a[start] = t10 }11 return a12}Проблема
Отсортировать массив, минимизируя количество обменов: за каждый проход по зоне — ровно один обмен, даже если внутри зоны всё перемешано.
Что вы видите
Столбики. Лаймовым подсвечен текущий кандидат в минимумы, циановым — тот, с кем сравниваем. Когда зона просканирована, минимум обменивается местами с первым столбиком зоны — и граница отсортированной части сдвигается вправо.
Как это работает
На каждом проходе алгоритм запоминает индекс минимального элемента зоны, а в конце меняет его местами с началом зоны. Сравнений всё те же O(n²), но обменов максимум n−1 — в разы меньше, чем у пузырька на перемешанных данных. Полезно, когда запись дорога, а чтение дёшево.
Пошаговый разбор
- 01
Зона
Неотсортированная часть начинается с индекса start.
- 02
Поиск минимума
Считаем a[start] минимумом и проходим зону, обновляя кандидата.
- 03
Один обмен
Меняем найденный минимум с a[start] местами.
- 04
Граница вправо
start++ — отсортированный префикс вырос.
Complexity и ограничения
Нестабильная сортировка: равные элементы могут поменяться местами. Обменов ≤ n−1.
Edge cases
- Уже отсортирован
Обменов не будет, но сравнения всё равно O(n²).
- Обратный порядок
Максимум обменов — по одному на проход.
- Дубликаты
Работает, но порядок равных не сохраняется.
Где встречается в реальности
Дорогая запись
Flash-память: запись изнашивает ячейки — минимум обменов важнее минимума сравнений.
Вложенные выборы
«Выбрать топ-3 из потока» — та же идея выбора экстремума.
Учебный контраст
Наглядно показывает разницу «сравнения» и «обмены» в сортировках.
Связанные алгоритмы
«Сортировка с одним обменом за проход»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.