Подготовка к алгоритмическим задачам

Сортировка пузырьком: полное руководство по классическому алгоритму

10 мин чтения

алгоритмы

сортировка

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

оптимизация

структуры данных

Почему сортировка пузырьком важна?

Сортировка пузырьком — это фундаментальный алгоритм сортировки, который позволяет оценить:

🧠 Понимание базовых принципов сортировки данных
⚡ Навыки реализации простых алгоритмов
🎯 Способность анализировать временную и пространственную сложность
🔍 Умение оптимизировать существующие алгоритмы
💼 Практические навыки применения в учебных и реальных задачах

Что такое сортировка пузырьком?

Сортировка пузырьком (Bubble Sort) — один из самых простых алгоритмов сортировки, который основан на многократном проходе по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно, и если порядок неверен — они меняются местами. Процесс повторяется, пока массив не будет отсортирован.

Название "пузырьковая сортировка" происходит от принципа работы алгоритма: более "легкие" элементы (с меньшими значениями) постепенно "всплывают" к началу массива, подобно пузырькам воздуха в воде.

Классическая формулировка:

Дан массив из n элементов. Требуется упорядочить его по возрастанию (или убыванию) значений элементов.

Пошаговый алгоритм сортировки пузырьком:

Сравниваем соседние элементы массива (индексы i и i+1)
Если они стоят в неправильном порядке, меняем их местами
Повторяем шаги 1-2 для всех пар соседних элементов от начала массива до конца
После первого полного прохода самый большой элемент оказывается в конце массива
Повторяем шаги 1-4, исключая из рассмотрения уже отсортированные элементы
Процесс продолжается до тех пор, пока весь массив не будет отсортирован

Примеры:

// Первый пример ✅
Input: [5, 3, 8, 4, 2]
1-й проход: [3, 5, 4, 2, 8] (8 переместилась в конец)
2-й проход: [3, 4, 2, 5, 8] (5 переместилась перед 8)
3-й проход: [3, 2, 4, 5, 8] (4 переместилась перед 5)
4-й проход: [2, 3, 4, 5, 8] (3 переместилась перед 4)
Output: [2, 3, 4, 5, 8]

// Второй пример ✅
Input: [9, 7, 5, 3, 1]
1-й проход: [7, 5, 3, 1, 9]
2-й проход: [5, 3, 1, 7, 9]
3-й проход: [3, 1, 5, 7, 9]
4-й проход: [1, 3, 5, 7, 9]
Output: [1, 3, 5, 7, 9]

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к реализации

Решение 1: Классическая реализация сортировки пузырьком 🔍

function bubbleSort(arr) {
  const n = arr.length;
  
  // Внешний цикл: количество проходов
  for (let i = 0; i < n - 1; i++) {
    
    // Внутренний цикл: сравнение соседних элементов
    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]];
      }
    }
  }
  
  return arr;
}

// Пример использования
const array = [5, 3, 8, 4, 2];
console.log(bubbleSort(array)); // [2, 3, 4, 5, 8]

Анализ решения:

✅ Простой и понятный алгоритм

✅ Минимальное использование дополнительной памяти (сортировка "на месте")

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

❌ Временная сложность O(n²) в худшем и среднем случаях

❌ Неэффективен для больших наборов данных

Решение 2: Оптимизированная сортировка пузырьком 🚀

function optimizedBubbleSort(arr) {
  const n = arr.length;
  
  // Внешний цикл: количество проходов
  for (let i = 0; i < n - 1; 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;
}

// Пример использования
const array = [5, 3, 8, 4, 2];
console.log(optimizedBubbleSort(array)); // [2, 3, 4, 5, 8]

Характеристики:

✅ Раннее завершение, если массив уже отсортирован

✅ Оптимальная временная сложность O(n) для уже отсортированного массива

✅ Сохраняет все преимущества классического варианта

❌ В худшем случае всё равно O(n²)

Решение 3: Двунаправленная сортировка пузырьком (сортировка коктейлем) 📈

function cocktailSort(arr) {
  let start = 0;
  let end = arr.length - 1;
  let swapped = true;
  
  while (swapped) {
    // Сброс флага в начале итерации
    swapped = false;
    
    // Проход слева направо (как в обычной сортировке пузырьком)
    for (let i = start; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    
    // Если не было обменов, массив отсортирован
    if (!swapped) {
      break;
    }
    
    // Уменьшаем end, так как самый большой элемент уже в конце
    end--;
    
    // Сбрасываем флаг для обратного прохода
    swapped = false;
    
    // Проход справа налево
    for (let i = end; i > start; i--) {
      if (arr[i] < arr[i - 1]) {
        [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
        swapped = true;
      }
    }
    
    // Увеличиваем start, так как самый маленький элемент уже в начале
    start++;
  }
  
  return arr;
}

Преимущества и недостатки:

✅ Более эффективная работа с "черепахами" (маленькими значениями в конце массива)

✅ Может быть быстрее обычной сортировки пузырьком на некоторых наборах данных

✅ Сохраняет стабильность сортировки

❌ Более сложная реализация

❌ Асимптотическая сложность всё равно O(n²)

Временная и пространственная сложность

Временная сложность сортировки пузырьком:

Худший случай (O(n²)): Когда массив отсортирован в порядке, обратном требуемому
Средний случай (O(n²)): На случайных наборах данных
Лучший случай (O(n)): Для оптимизированной версии на уже отсортированном массиве

Пространственная сложность:

O(1): Сортировка выполняется "на месте", требуется только фиксированное количество дополнительной памяти

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

Алгоритм	Лучший случай	Средний случай	Худший случай	Память	Стабильность
Пузырьковая сортировка	O(n)	O(n²)	O(n²)	O(1)	Да
Сортировка вставками	O(n)	O(n²)	O(n²)	O(1)	Да
Быстрая сортировка	O(n log n)	O(n log n)	O(n²)	O(log n)	Нет
Сортировка слиянием	O(n log n)	O(n log n)	O(n log n)	O(n)	Да
Сортировка выбором	O(n²)	O(n²)	O(n²)	O(1)	Нет

Когда использовать сортировку пузырьком?

Сортировка пузырьком особенно полезна в следующих случаях:

📚 Образовательные цели: Идеальна для понимания базовых принципов сортировки
🧩 Маленькие наборы данных: Для массивов с небольшим количеством элементов (до 100)
✅ Почти отсортированные массивы: Оптимизированная версия эффективна для массивов, где большинство элементов уже на своих местах
🔄 Ограниченная память: Когда важно минимальное использование дополнительной памяти
🛡️ Простота реализации: Когда требуется быстро реализовать сортировку без сложной логики

Оптимизации и улучшения

Сокращение числа итераций

function improvedBubbleSort(arr) {
  let n = arr.length;
  
  // Внешний цикл
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    let newn = 0;
    
    // Внутренний цикл
    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;
        newn = j + 1; // Запоминаем позицию последнего обмена
      }
    }
    
    // Если обменов не было, завершаем сортировку
    if (!swapped) {
      break;
    }
    
    // Обновляем n до позиции последнего обмена
    n = newn;
  }
  
  return arr;
}

Рекурсивная реализация сортировки пузырьком

function recursiveBubbleSort(arr, n = arr.length) {
  // Базовый случай
  if (n === 1) {
    return arr;
  }
  
  // Один проход сортировки пузырьком
  for (let i = 0; i < n - 1; i++) {
    if (arr[i] > arr[i + 1]) {
      [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
    }
  }
  
  // Рекурсивный вызов для оставшихся элементов
  return recursiveBubbleSort(arr, n - 1);
}

Параллельная сортировка пузырьком

// Концептуальный пример для многопоточных сред
async function parallelBubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n; i++) {
    // Четно-нечетная сортировка (odd-even sort)
    // Сначала сравниваем и сортируем все четные пары
    await Promise.all(
      Array.from({ length: Math.floor(n / 2) }, (_, j) => {
        const index = j * 2;
        if (index + 1 < n && arr[index] > arr[index + 1]) {
          [arr[index], arr[index + 1]] = [arr[index + 1], arr[index]];
        }
        return Promise.resolve();
      })
    );
    
    // Затем сравниваем и сортируем все нечетные пары
    await Promise.all(
      Array.from({ length: Math.floor((n - 1) / 2) }, (_, j) => {
        const index = j * 2 + 1;
        if (index + 1 < n && arr[index] > arr[index + 1]) {
          [arr[index], arr[index + 1]] = [arr[index + 1], arr[index]];
        }
        return Promise.resolve();
      })
    );
  }
  
  return arr;
}

Визуализация работы алгоритма

Рассмотрим процесс сортировки массива [5, 1, 4, 2, 8]:

Первый проход:

Сравниваем 5 > 1? Да, меняем. Массив: [1, 5, 4, 2, 8]
Сравниваем 5 > 4? Да, меняем. Массив: [1, 4, 5, 2, 8]
Сравниваем 5 > 2? Да, меняем. Массив: [1, 4, 2, 5, 8]
Сравниваем 5 > 8? Нет, оставляем. Массив: [1, 4, 2, 5, 8]

Второй проход:

Сравниваем 1 > 4? Нет, оставляем. Массив: [1, 4, 2, 5, 8]
Сравниваем 4 > 2? Да, меняем. Массив: [1, 2, 4, 5, 8]
Сравниваем 4 > 5? Нет, оставляем. Массив: [1, 2, 4, 5, 8]
Сравниваем 5 > 8? Нет, оставляем. Массив: [1, 2, 4, 5, 8]

Третий проход:

В оптимизированной версии заметим, что обменов не было, и завершим сортировку.
В классической версии выполним еще два прохода, но обменов не произойдет.

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

Распространенные ошибки при реализации

🤦‍♂️ Неправильные границы циклов: Отсутствие n - i - 1 во внутреннем цикле, что приводит к лишним сравнениям
😅 Забывание оптимизации: Неиспользование флага swapped для раннего завершения
🐛 Ошибки при обмене элементов: Неправильная реализация обмена значений переменных
😕 Неэффективное использование: Применение сортировки пузырьком к большим массивам

Практические применения

Учебные цели

Сортировка пузырьком часто используется в образовательных целях как первый алгоритм сортировки, который изучают студенты в области информатики.

Маленькие наборы данных

В реальных приложениях, где требуется сортировка небольших массивов с минимальным использованием памяти.

Проверка почти отсортированных данных

Оптимизированная версия эффективна для проверки и коррекции почти отсортированных массивов.

Встроенные системы

В устройствах с ограниченными ресурсами, где важна простота реализации и минимальное использование памяти.

Заключение

Сортировка пузырьком — это классический алгоритм сортировки, который:

🤹‍♂️ Прост в понимании и реализации
📊 Эффективен для маленьких или почти отсортированных массивов
🧠 Демонстрирует ключевые принципы сравнения и обмена элементов
🔄 Может быть оптимизирован различными способами
🔍 Служит отличной базой для изучения более сложных алгоритмов сортировки

Хотя сортировка пузырьком редко используется в промышленных приложениях из-за своей временной сложности O(n²), понимание этого алгоритма закладывает прочный фундамент для изучения более эффективных методов сортировки и алгоритмической оптимизации. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование