Bubble Sort (Сортировка пузырьком)
Краткое описание
Простейший алгоритм сортировки, который многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они в неправильном порядке. Большие элементы “всплывают” к концу массива, как пузырьки. Эффективен только на малых или почти отсортированных данных.
Когда использовать
- Почти отсортированные данные — оптимизированная версия bubble sort имеет O(n) сложность для уже отсортированных массивов
- Маленькие массивы — когда производительность не критична и важна простота кода
- Образовательные цели — один из самых простых для понимания алгоритмов сортировки
- Стабильная сортировка — сохраняет относительный порядок равных элементов
- Ограниченная память — алгоритм использует O(1) дополнительной памяти (in-place сортировка)
- Обнаружение отсортированности — может быстро проверить, отсортирован ли массив
Когда не стоит использовать:
- Большие массивы — в среднем и худшем случаях имеет O(n²) сложность
- Когда производительность критична — существуют намного более быстрые алгоритмы
- Системы с медленным доступом к памяти — алгоритм делает много операций swap
С объяснением логики работы
/**
* Сортировка пузырьком (Bubble Sort)
* Принцип: сравниваем соседние элементы и меняем их местами, если они в неправильном порядке.
* Самые большие элементы "всплывают" к концу массива, как пузырьки.
*/
function bubbleSort(arr) {
// Внешний цикл определяет количество проходов по массиву
// С каждым проходом один самый большой элемент "всплывает" в конец
// Поэтому нужно (n-1) проходов для сортировки n элементов
for (let i = 0; i < arr.length - 1; i++) {
// Флаг для оптимизации: отслеживаем, были ли обмены на этом проходе
// Если за весь проход не было ни одного обмена — массив уже отсортирован
let swapped = false;
// Внутренний цикл проходит по неотсортированной части массива
// (arr.length - i - 1) потому что после каждого прохода внешнего цикла
// последние i элементов уже на своих местах (самые большие "всплыли")
for (let j = 0; j < arr.length - i - 1; j++) {
// Сравниваем два соседних элемента
// Если левый больше правого — они в неправильном порядке
if (arr[j] > arr[j + 1]) {
// Меняем элементы местами используя деструктуризацию массива
// Это эквивалентно: temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// Отмечаем, что был обмен
// Это означает, что массив ещё не отсортирован
swapped = true;
}
}
// Оптимизация: если за весь проход не было обменов
// значит массив уже отсортирован и можно прекратить работу досрочно
if (!swapped) {
// Прерываем внешний цикл — сортировка завершена
break;
}
// После каждого прохода самый большой элемент из оставшихся
// гарантированно находится на своей финальной позиции в конце массива
}
// Возвращаем отсортированный массив
// Массив сортируется "на месте" (in-place), но возврат удобен для цепочки вызовов
return arr;
}
// Пример использования
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("Исходный массив:", numbers);
bubbleSort(numbers);
console.log("Отсортированный массив:", numbers);
// Пример с почти отсортированным массивом (где bubble sort эффективен)
const almostSorted = [1, 2, 3, 5, 4, 6];
console.log("Почти отсортированный:", almostSorted);
bubbleSort(almostSorted);
console.log("Результат:", almostSorted);С анализом сложностей
/**
* Сортировка пузырьком (Bubble Sort) с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n) — массив уже отсортирован, один проход без обменов, флаг swapped = false
* - Средний случай: O(n²) — элементы в произвольном порядке, требуется ~n²/2 сравнений и обменов
* - Худший случай: O(n²) — массив отсортирован в обратном порядке, максимум сравнений и обменов
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(1) — требуется только константное количество памяти для переменных (i, j, swapped, temp)
* - Сортировка происходит "на месте" (in-place), без создания дополнительных структур данных
*
* КОЛИЧЕСТВО ОПЕРАЦИЙ:
* - Сравнения (худший/средний): (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2
* - Обмены (худший): O(n²), (лучший): O(0), (средний): O(n²/2)
*
* ОСОБЕННОСТИ:
* - Адаптивный: производительность улучшается на почти отсортированных данных
* - Стабильный: сохраняет порядок равных элементов
*/
function bubbleSort(arr) {
// Внешний цикл: выполняется максимум (n-1) раз
// В лучшем случае (уже отсортированный массив): O(1) итерация благодаря флагу swapped
// В худшем случае: O(n) итераций
for (let i = 0; i < arr.length - 1; i++) {
// Флаг swapped — O(1) операция инициализации
// Критически важен для достижения O(n) в лучшем случае
// Без него даже отсортированный массив будет обрабатываться за O(n²)
let swapped = false;
// Внутренний цикл: количество итераций уменьшается с каждым проходом
// Проход 1: (n-1) сравнений
// Проход 2: (n-2) сравнений
// ...
// Проход n-1: 1 сравнение
//
// ЛУЧШИЙ СЛУЧАЙ (массив отсортирован):
// - Внешний цикл: 1 итерация
// - Внутренний цикл: (n-1) итераций
// - Итого: n-1 сравнений = O(n)
//
// ХУДШИЙ/СРЕДНИЙ СЛУЧАЙ:
// - Общее количество сравнений: (n-1) + (n-2) + ... + 1 = n(n-1)/2
// - Итого: O(n²)
for (let j = 0; j < arr.length - i - 1; j++) {
// Сравнение — O(1) операция
//
// ЛУЧШИЙ СЛУЧАЙ: (n-1) сравнений, 0 обменов
// ХУДШИЙ СЛУЧАЙ: n(n-1)/2 сравнений, n(n-1)/2 обменов
// СРЕДНИЙ СЛУЧАЙ: n(n-1)/2 сравнений, примерно n(n-1)/4 обменов
if (arr[j] > arr[j + 1]) {
// Swap операция — O(1) по времени
// Использует O(1) дополнительной памяти (временные переменные в деструктуризации)
//
// ВАЖНО: Bubble Sort делает больше операций записи, чем Selection Sort
// Selection Sort: максимум O(n) swap-операций
// Bubble Sort: максимум O(n²) swap-операций
//
// Это делает Bubble Sort медленнее на системах с дорогой операцией записи
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
// Установка флага — O(1)
swapped = true;
}
}
// Проверка флага — O(1) операция
//
// Эта оптимизация превращает алгоритм в АДАПТИВНЫЙ:
// - Если массив уже отсортирован → O(n)
// - Если массив почти отсортирован → O(n) до O(n²) в зависимости от количества инверсий
// - Если массив в случайном порядке → O(n²)
//
// Без этой проверки алгоритм всегда работает за O(n²), даже на отсортированных данных
if (!swapped) {
break;
}
}
// ИТОГОВАЯ СЛОЖНОСТЬ:
// Время: O(n) в лучшем, O(n²) в среднем и худшем
// Память: O(1) — только переменные i, j, swapped
//
// СРАВНЕНИЕ С ДРУГИМИ АЛГОРИТМАМИ:
// - Quick Sort: в среднем O(n log n), но O(n²) в худшем и O(n log n) на отсортированных
// - Merge Sort: всегда O(n log n), но требует O(n) дополнительной памяти
// - Bubble Sort: побеждает на малых и почти отсортированных массивах благодаря O(n) лучшему случаю
return arr;
}
// Примеры для демонстрации разной сложности:
// ЛУЧШИЙ СЛУЧАЙ: O(n) — один проход, без обменов
const best = [1, 2, 3, 4, 5];
// Выполнится: 4 сравнения, 0 обменов, 1 проход
// ХУДШИЙ СЛУЧАЙ: O(n²) — максимум проходов и обменов
const worst = [5, 4, 3, 2, 1];
// Выполнится: 10 сравнений, 10 обменов, 4 прохода
// Формула: n(n-1)/2 = 5*4/2 = 10
// СРЕДНИЙ СЛУЧАЙ: O(n²) — произвольный порядок
const average = [3, 5, 1, 4, 2];
// Выполнится: примерно 10 сравнений, ~5-7 обменов, 2-4 прохода