Яка складність сортування бульбашкою?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Сортування бульбашкою має таку часову складність: у найкращому випадку O(n) (за наявності оптимізації раннього виходу), у середньому і найгіршому випадках - O(n^2). Просторова складність O(1), алгоритм стійкий (stable) і виконується на місці (in-place).

Детальний розбір

Часова складність

Найкращий випадок: O(n), якщо використовується прапорець "чи були обміни" і масив вже відсортований (алгоритм завершиться після одного проходу).
Середній випадок: O(n^2) - для довільних даних потрібно приблизно n·(n-1)/2 порівнянь.
Найгірший випадок: O(n^2) - для повністю оберненого сортування кількість порівнянь і обмінів максимальна.

Просторова складність

O(1) - сортування виконується на місці і потребує лише сталого обсягу додаткової пам'яті (змінні циклу і прапорець обміну).

Стійкість і адаптивність

Стійкий: рівні елементи зберігають відносний порядок.
Адаптивний (за наявності оптимізації): якщо масив майже відсортований, завершується швидше, аж до O(n).

Скільки порівнянь і обмінів

Порівняння в найгіршому (і середньому) випадку: n·(n-1)/2.
Обміни в найгіршому випадку: n·(n-1)/2; у найкращому - 0 (якщо використовуємо ранній вихід).
Без прапорця раннього виходу навіть у відсортованому масиві буде виконано ~n·(n-1)/2 порівнянь.

Оптимізації

Прапорець swapped: якщо за прохід не було обмінів - масив відсортований, виходимо (дає найкращий випадок O(n)).
Скорочення межі: після кожного проходу останній елемент опиняється на своєму місці - зменшуємо довжину внутрішнього циклу.
Запам'ятовування позиції останнього обміну: дозволяє ще сильніше зменшувати діапазон наступного проходу.
Двонапрямлена (cocktail) бульбашка: жене великі елементи вправо, а малі - вліво за один цикл, пришвидшуючи роботу на деяких даних.

Коли використовувати, а коли ні

Використовувати: для навчальних цілей, дуже малих масивів, майже відсортованих даних, коли важлива простота реалізації і стійкість.
Не використовувати: для середніх і великих масивів у продакшені - є алгоритми O(n log n), що працюють швидше (quicksort, mergesort, heapsort).

Приклад: оптимізоване сортування бульбашкою (JavaScript, ES6)

function bubbleSort(arr) {
  const a = arr.slice(); // не мутуємо вихідний масив
  let n = a.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]]; // обмін
        swapped = true;
      }
    }
    n--; // останній елемент вже на своєму місці
  } while (swapped);
  return a;
}

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

Приклад: двонапрямлене (cocktail) сортування бульбашкою

function cocktailSort(arr) {
  const a = arr.slice();
  let left = 0;
  let right = a.length - 1;
  let swapped = true;

  while (swapped) {
    swapped = false;
    // прохід зліва направо
    for (let i = left; i < right; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    right--;
    if (!swapped) break;

    swapped = false;
    // прохід справа наліво
    for (let i = right; i > left; i--) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    left++;
  }
  return a;
}

console.log(cocktailSort([3, 0, 2, 5, -1, 4, 1])); // [-1, 0, 1, 2, 3, 4, 5]

Порівняння з іншими алгоритмами

Insertion sort: теж O(n^2), але зазвичай швидше за бульбашку на практиці; найкращий випадок O(n) без додаткової пам'яті, стійкий.
Selection sort: O(n^2), мінімум обмінів (O(n)), але нестійкий; часто швидше за бульбашку за кількістю записів у пам'ять.
Quicksort / Mergesort / Heapsort: асимптотично швидші на великих n - O(n log n), кращий вибір для продакшену.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.