Какая сложность сортировки пузырьком?

Сложность сортировки пузырьком (bubble sort) — O(n²) в среднем и худшем случае, O(n) в лучшем (уже отсортированный массив с оптимизацией). По памяти — O(1).

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

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

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

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {        // n
    for (let j = 0; j < arr.length - i - 1; j++) { // n
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // обмен
      }
    }
  }
}

n × n = O(n²).

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

С оптимизацией (флаг «были ли обмены»): если за проход не было обменов — массив отсортирован, выходим. На уже отсортированном массиве — один проход O(n):

let swapped = false;
// если за проход swapped === false → выход

Пространственная сложность: O(1)

Сортирует на месте, доп. память не нужна.

Особенности

• Стабильная — сохраняет порядок равных элементов.
• Простая для понимания, но неэффективная — O(n²) плоха для больших данных.
• Учебная сортировка; на практике используют O(n log n) (quicksort, merge sort, встроенный sort).

Коротко для собеседования

Пузырьковая сортировка — O(n²) в среднем и худшем (два вложенных цикла со сравнением и обменом соседей), O(n) в лучшем (с флагом обменов на уже отсортированном). Память O(1) (in-place), стабильная. Проста, но неэффективна — на практике используют O(n log n) (quicksort, merge sort).