Сортировка пузырьком

Алгоритмы сортировкиЛёгкий

Описание

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

Зачем это нужно

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

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

Начальное состояние: неотсортированный массив

Неотсортировано

Сравнение

Обмен

Отсортировано

Шаг 1 из 50

Скорость:

Как работает алгоритм

Сортировка пузырьком получила своё название из-за того, как большие элементы постепенно «всплывают» в конец массива, подобно пузырькам воздуха в воде. Алгоритм совершает несколько проходов по массиву, меняя местами соседние элементы, стоящие в неправильном порядке.

1. Начало с первого элемента

Начинаем с первого элемента массива. Будем сравнивать каждую пару соседних элементов при проходе слева направо.

2. Сравнение соседних элементов

Сравниваем текущий элемент со следующим. Если текущий элемент больше следующего, значит они стоят в неправильном порядке.

3. Обмен при необходимости

Если элементы стоят в неправильном порядке, меняем их местами. Возможны два варианта:

arr[j] > arr[j+1] — меняем элементы местами, больший элемент сдвигается вправо.
arr[j] ≤ arr[j+1] — обмен не нужен, переходим к следующей паре.

4. Повторение проходов

После одного полного прохода наибольший из неотсортированных элементов гарантированно оказывается в конце. Повторяем проходы для оставшейся неотсортированной части, пока обмены не прекратятся — массив отсортирован.

Пример: сортировка массива [5, 3, 8, 1, 2]

Проход 1: [5,3,8,1,2] → [3,5,8,1,2] → [3,5,8,1,2] → [3,5,1,8,2] → [3,5,1,2,8]. Наибольший элемент 8 теперь в конце.

Проход 2: [3,5,1,2,8] → [3,5,1,2,8] → [3,1,5,2,8] → [3,1,2,5,8]. Элемент 5 на месте. Продолжаем до отсортированного: [1,2,3,5,8].

Сложность

Лучший случайO(n)

Средний случайO(n²)

Худший случайO(n²)

Сложность по памятиO(1)

Анализ сложности

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

O(n) — лучший случай, когда массив уже отсортирован. С оптимизацией (проверка, были ли обмены) алгоритм делает один проход и завершает работу.

O(n²) — средний случай. Для случайно упорядоченного массива алгоритм совершает примерно n²/2 сравнений и n²/4 обменов в среднем.

O(n²) — худший случай, когда массив отсортирован в обратном порядке. Каждую пару соседних элементов нужно обменять на каждом проходе, что даёт n·(n-1)/2 сравнений.

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

O(1) — сортировка пузырьком выполняется «на месте». Она использует лишь константный объём дополнительной памяти для временных переменных при обмене (и флаг swapped для оптимизации).

Стабильная сортировка — равные элементы не меняют относительный порядок, потому что обмен происходит только когда arr[j] > arr[j+1] (строго больше), а не при равенстве.

Оптимизация раннего завершения

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

Пример кода
function bubbleSort(arr: number[]): void {
  const n = arr.length;

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

    // Last i elements are already in place
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap adjacent elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // If no swaps occurred, array is sorted
    if (!swapped) break;
  }
}

// Usage example
const unsorted = [64, 34, 25, 12, 22, 11, 90];
const sorted = [...unsorted]; // Copy to avoid mutating original
bubbleSort(sorted);
console.log(sorted); // [11, 12, 22, 25, 34, 64, 90]

Примеры использования в реальных задачах

Обучение принципам сортировки

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

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

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

Малые наборы данных

Для очень маленьких массивов (5–10 элементов) простота сортировки пузырьком может сделать её конкурентоспособной с более сложными алгоритмами благодаря низким накладным расходам и хорошей локальности кэша.

Проверка отсортированности массива

Один проход сортировки пузырьком (без обменов) — это по сути проверка O(n) того, отсортирован ли уже массив. Полезно как предварительная проверка перед запуском более дорогого алгоритма.

Графика и заливка полигонов

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

Задачи на LeetCode

#26Remove Duplicates from Sorted Array

Лёгкая

#88Merge Sorted Array

Лёгкая