Bubble Sort (Сортировка пузырьком)

Bubble sort — простейший алгоритм сортировки, который многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, пока массив не станет отсортированным.

Зачем нужно

Bubble sort — учебный алгоритм для понимания концепции сортировки. На практике не используется из-за O(n^2) сложности, но идеально подходит для изучения: прост в реализации и визуализации.

Где используется

  • Обучение основам алгоритмов
  • Сортировка очень маленьких массивов (< 10 элементов)
  • Проверка: массив почти отсортирован (с оптимизацией — O(n))
  • Понимание базы для более сложных сортировок

Предпосылки

Алгоритм

1. Пройти по массиву слева направо
2. Сравнить каждую пару соседних элементов
3. Если левый > правого — поменять местами
4. После прохода: максимальный элемент "всплыл" в конец
5. Повторить для оставшейся части (без последнего)
6. Пока есть обмены — продолжать

Визуализация

Массив: [5, 3, 8, 1, 2]

Проход 1:
[5, 3, 8, 1, 2]  → 5>3 → swap → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → 5<8 → ok
[3, 5, 8, 1, 2]  → 8>1 → swap → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2]  → 8>2 → swap → [3, 5, 1, 2, 8] ← 8 на месте

Проход 2:
[3, 5, 1, 2, 8]  → 3<5 → ok
[3, 5, 1, 2, 8]  → 5>1 → swap → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8]  → 5>2 → swap → [3, 1, 2, 5, 8] ← 5 на месте

Проход 3:
[3, 1, 2, 5, 8]  → 3>1 → swap → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8]  → 3>2 → swap → [1, 2, 3, 5, 8] ← 3 на месте

Проход 4:
[1, 2, 3, 5, 8]  → нет обменов → СТОП!

Результат: [1, 2, 3, 5, 8]

Реализация в JavaScript

Базовая версия

function bubbleSort(array) {
  const arr = [...array]; // не мутируем оригинал
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]

Оптимизированная версия (early exit)

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

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // Если за весь проход не было обменов — массив отсортирован
    if (!swapped) break;
  }

  return arr;
}

// Для почти отсортированного массива — завершается за 1-2 прохода
console.log(bubbleSortOptimized([1, 2, 3, 5, 4])); // 1 проход + 1 проверочный

Сортировка объектов

function bubbleSortBy(array, compareFn) {
  const arr = [...array];
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    for (let j = 0; j < n - 1 - i; j++) {
      if (compareFn(arr[j], arr[j + 1]) > 0) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return arr;
}

const users = [
  { name: 'Charlie', age: 35 },
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
];

// Сортировка по возрасту
const byAge = bubbleSortBy(users, (a, b) => a.age - b.age);
// [{ name: 'Bob', age: 25 }, { name: 'Alice', age: 30 }, { name: 'Charlie', age: 35 }]

Сложность

Случай Время Память Описание
Лучший O(n) O(1) Уже отсортирован (с оптимизацией)
Средний O(n^2) O(1) Случайный порядок
Худший O(n^2) O(1) Обратный порядок

Стабильная сортировка: да (равные элементы сохраняют относительный порядок).

In-place: да (не требует дополнительной памяти).

Сравнение с другими сортировками

Алгоритм Лучший Средний Худший Стабильная In-place
Bubble sort O(n) O(n^2) O(n^2) Да Да
Quick sort O(n log n) O(n log n) O(n^2) Нет Да
Merge sort O(n log n) O(n log n) O(n log n) Да Нет
JS Array.sort() O(n log n) O(n log n) O(n log n) Да Зависит

Частые ошибки

  1. Использовать на больших данных. На 10 000 элементов bubble sort в ~100 раз медленнее merge sort
  2. Забывать оптимизацию early exit. Без неё даже отсортированный массив проходится n^2 раз
  3. Путать стабильность. Bubble sort стабильна, но quick sort — нет. Это важно при сортировке объектов

Практика

  1. Реализуйте bubble sort без подглядывания
  2. Добавьте счётчик сравнений и обменов — сравните для отсортированного и случайного массива
  3. Замерьте время: bubbleSort vs Array.sort() на массиве из 10 000 случайных чисел
// Замер производительности
function benchmark(fn, data) {
  const start = performance.now();
  fn(data);
  return (performance.now() - start).toFixed(2) + ' ms';
}

const random = Array.from({ length: 10000 }, () => Math.random * 10000);
console.log('Bubble:', benchmark(bubbleSort, random));
console.log('Native:', benchmark(arr => [...arr].sort((a, b) => a - b), random));

Связанные темы

Ресурсы