Сортировка пузырьком
Соседние пары меняются местами, пока максимум не «всплывёт» в конец — и так для каждой позиции.
1function bubbleSort(a: number[]): number[] {2 for (let end = a.length - 1; end > 0; end--) {3 for (let i = 0; i < end; i++) {4 if (a[i] > a[i + 1]) {5 const t = a[i]6 a[i] = a[i + 1]7 a[i + 1] = t8 }9 }10 }11 return a12}Проблема
Отсортировать массив, имея только одну операцию: сравнить двух соседей и при необходимости поменять их местами. Никакой дополнительной памяти, никакой хитрой структуры — только терпеливые проходы.
Что вы видите
Столбики разной высоты. На каждом шаге подсвечивается пара соседей; если левый выше — они плавно меняются местами. После прохода самый высокий столбик гарантированно стоит в правом конце и фиксируется.
Как это работает
За один проход максимум «всплывает» в крайнюю правую позицию — как пузырёк воздуха поднимается на поверхность. Следующий проход игнорирует уже зафиксированный хвост. n проходов × до n сравнений = O(n²) — медленно для больших данных, но это простейшая сортировка, на которой видно саму механику «сравни–обменяй».
Пошаговый разбор
- 01
Пара соседей
Сравниваем a[i] и a[i+1]: если порядок нарушен — обмен.
- 02
Проход
Идём слева направо до конца зоны; максимум остаётся в крайней правой позиции.
- 03
Фиксация хвоста
Отсортированный хвост закрашивается и больше не участвует.
- 04
Повтор
Зона уменьшается на единицу с каждым проходом.
- 05
Финал
Зона длины 1 — массив отсортирован.
Complexity и ограничения
Стабильная сортировка (равные элементы не меняют порядок). На месте, O(1) памяти.
Edge cases
- Уже отсортирован
Можно остановиться, если в проходе не было обменов — оптимизация до O(n).
- Обратный порядок
Худший случай: максимум обменов n(n−1)/2.
- Два элемента
Один проход — один обмен. Минимальная осмысленная сортировка.
Где встречается в реальности
Учебный эталон
Первая сортировка в любом курсе: механику «сравни–обменяй» видно голыми глазами.
Почти отсортированные данные
С ранним выходом — быстра, когда массив чуть-чуть перемешан.
Аппаратные сортировочные сети
Параллельные compare-exchange схемы — родственники пузырька.
Связанные алгоритмы
«Почему максимум сам «всплывает» в конец массива?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.