Пузырьковая сортировка
Сравниваем соседние значения слева направо и меняем их местами, если левое больше. Каждый проход переносит наибольшее оставшееся значение в конец неотсортированной части.
До 24 значений. Попробуйте повторы или отрицательные числа.
Шаг 0 / 23: Исходный массив. Сравниваем соседние значения слева направо.
Массив: [5, 2, 4, 2, 1]
Сравнения: 0 · Записи: 0
Зелёный — значения на окончательных местах. Подсвеченные столбцы — текущее сравнение или обмен. Позиции считаются с нуля.
Что остаётся отсортированным
После каждого прохода отсортированный хвост растёт на один элемент: его значения уже стоят на окончательных местах. Следующий проход пропускает этот хвост. Если за полный проход не было обменов, весь массив отсортирован и алгоритм завершается досрочно.
Почему сортировка стабильна
Соседи меняются местами, только если левое значение строго больше. Равные значения не пересекаются и сохраняют исходный порядок. В [5, 2, 4, 2, 1] первая двойка останется перед второй.
Сложность
- Уже отсортированный вход
- O(n)
- Средний и худший случай
- O(n²)
- Дополнительная память самого алгоритма
- O(1)
Визуализатор хранит полную историю состояний. Её память — O(n × число шагов), до O(n³) в этой реализации. Это отдельные затраты, отличные от памяти самой сортировки.
Реализация на JavaScript
Эта обёртка копирует вход перед сортировкой, поэтому показанная функция дополнительно использует O(n) памяти.
function bubbleSort(values) {
const result = [...values];
for (let end = result.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++) {
if (result[i] > result[i + 1]) {
[result[i], result[i + 1]] = [result[i + 1], result[i]];
swapped = true;
}
}
if (!swapped) break;
}
return result;
}Видеоразбор
Работает на AlgiViz
Алгоритм пузырьковой сортировки определён на этом сайте. AlgiViz предоставляет неизменяемые состояния операций с массивом, временную шкалу и canvas-отрисовку. Каждый обмен считается двумя записями в массив.