Пузырьковая сортировка

Пузырьковая сортировка — простейший алгоритм, с которого начинается изучение сортировок. Он медленный, но идеально иллюстрирует принцип: постепенно «выталкивать» большие элементы на нужное место. Разберём пошагово с визуализацией и напишем код.

🫧 Принцип: «пузыри» всплывают вправо

Представьте аквариум с пузырьками разного размера. Большие пузырьки поднимаются быстрее, маленькие — медленнее. Вот именно по этому принципу работает пузырьковая сортировка — большие элементы «всплывают» вправо с каждым проходом.

Алгоритм очень простой. Мы идём по массиву слева направо и сравниваем каждую пару соседних элементов. Если левый больше правого — меняем их местами. Так самый большой элемент за один проход окажется в самом конце. Потом повторяем для оставшейся части.

📊 Пошаговая визуализация: [5, 3, 8, 1, 4]

Разберём пошагово. Проход 1: сравниваем пары соседей и меняем местами, если нужно. После первого прохода максимальный элемент (8) встаёт на своё место.

💻 Базовая реализация

Код пузырьковой сортировки — один из самых коротких и понятных в алгоритмике. Два вложенных цикла: внешний считает проходы, внутренний идёт по элементам.

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n; i++) {           // внешний: n проходов
    for (let j = 0; j < n - i - 1; j++) { // внутренний: каждый раз на 1 короче
      if (arr[j] > arr[j + 1]) {
        // меняем местами (деструктуризация ES6)
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

console.log(bubbleSort([5, 3, 8, 1, 4]));
// [1, 3, 4, 5, 8]

Почему внутренний цикл идёт до n - i - 1? После каждого прохода i последних элементов уже отсортированы и стоят на своих местах. Нет смысла проверять их снова.

🚀 Оптимизация: флаг для раннего выхода

Базовая реализация всегда делает n² сравнений — даже если массив уже отсортирован! Это расточительно. Добавим простую оптимизацию: если за целый проход не было ни одной замены — массив уже отсортирован, выходим досрочно.

function bubbleSortOptimized(arr) {
  const n = arr.length;

  for (let i = 0; i < n; i++) {
    let swapped = false; // флаг: были ли замены в этом проходе?

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true; // была замена — отмечаем
      }
    }

    if (!swapped) {
      // Если ни одной замены — массив уже отсортирован!
      break;
    }
  }

  return arr;
}

// Для уже отсортированного массива — всего один проход!
console.log(bubbleSortOptimized([1, 2, 3, 4, 5]));
// [1, 2, 3, 4, 5] — быстро! O(n) в лучшем случае

Эта оптимизация меняет лучший случай с O(n²) на O(n). Если передать уже отсортированный массив — алгоритм сделает всего один проход и выйдет.

🔢 Почему сложность именно O(n²)

Посчитаем количество сравнений для массива из n элементов:

• Проход 1: n−1 сравнений
• Проход 2: n−2 сравнений
• Проход 3: n−3 сравнений
• ... и так до последнего прохода: 1 сравнение

Итого: (n−1) + (n−2) + ... + 1 = n(n−1)/2. При больших n это примерно n²/2. В Big O константы отбрасываем — получаем O(n²).

// Для n = 5 элементов:
// Проход 0: 4 сравнения (j от 0 до 3)
// Проход 1: 3 сравнения (j от 0 до 2)
// Проход 2: 2 сравнения (j от 0 до 1)
// Проход 3: 1 сравнение  (j = 0)
// Итого: 4 + 3 + 2 + 1 = 10 сравнений = 5*4/2

// Для n = 1000:
// 1000 * 999 / 2 = 499 500 сравнений

// Для n = 1 000 000:
// ~500 000 000 000 сравнений = миллиард!

✅ Когда пузырьковая сортировка полезна

Несмотря на все ограничения, есть ситуации, где пузырьковая сортировка — разумный выбор:

✅ Итоги урока

• Пузырьковая сортировка сравнивает соседние элементы и переставляет их — большие «всплывают» вправо
• За каждый полный проход самый большой из оставшихся элементов встаёт на своё место
• Два вложенных цикла → сложность O(n²) в среднем и худшем случае
• Флаг swapped позволяет выйти досрочно — лучший случай становится O(n)
• Для массива [5, 3, 8, 1, 4] нужно 4 прохода и 10 сравнений
• На практике не используется для больших данных — только учебные цели и маленькие массивы