Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Яка складність сортування бульбашкою?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Сортування бульбашкою має таку часову складність: у найкращому випадку 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), кращий вибір для продакшену.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати569 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.