Як працює BubbleSort?

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

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

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

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

Ідея алгоритму

Йдемо зліва направо по масиву і порівнюємо сусідні елементи.
Якщо пара в неправильному порядку - міняємо елементи місцями.
До кінця проходу максимальний елемент «спливає» в кінець масиву (на своє підсумкове місце).
Повторюємо нові проходи, ігноруючи вже відсортований хвіст, доти, доки за прохід не відбулося жодної перестановки.

Інваріант: після i-го повного проходу останні i елементів - на своїх остаточних місцях.

Покроковий приклад

Масив: [5, 1, 4, 2, 8]

Прохід 1:
- порівняти 5 і 1 → 5>1, swap → [1, 5, 4, 2, 8]
- порівняти 5 і 4 → 5>4, swap → [1, 4, 5, 2, 8]
- порівняти 5 і 2 → 5>2, swap → [1, 4, 2, 5, 8]
- порівняти 5 і 8 → 5≤8, без swap → [1, 4, 2, 5, 8]
Хвіст: 8 стоїть на місці.

Прохід 2 (без останнього елемента):
- 1 і 4 → ок
- 4 і 2 → swap → [1, 2, 4, 5, 8]
- 4 і 5 → ок
Хвіст: 5, 8 стоять на місці.

Прохід 3:
- 1 і 2 → ок
- 2 і 4 → ок
Немає перестановок → ранній вихід. Підсумок: [1, 2, 4, 5, 8]

Псевдокод

bubbleSort(A):
  n = length(A)
  for i from 0 to n-2:
    swapped = false
    for j from 0 to n-2-i:
      if A[j] > A[j+1]:
        swap A[j], A[j+1]
        swapped = true
    if not swapped:
      break  // ранній вихід, масив уже відсортований
  return A

Реалізація (JavaScript)

// Базова версія (повертає новий масив)
function bubbleSort(arr) {
  const a = arr.slice();
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

// Оптимізована версія: ранній вихід + межа за останньою перестановкою
function bubbleSortOptimized(arr) {
  const a = arr.slice();
  let n = a.length;
  while (n > 1) {
    let newN = 0; // позиція останньої перестановки
    for (let j = 0; j < n - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        newN = j + 1;
      }
    }
    if (newN === 0) break; // уже відсортовано
    n = newN; // хвіст після newN уже відсортований
  }
  return a;
}

// Двостороння версія (Cocktail Shaker Sort)
function cocktailShakerSort(arr) {
  const a = arr.slice();
  let start = 0;
  let end = a.length - 1;
  let swapped = true;
  while (swapped) {
    swapped = false;
    for (let i = start; i < end; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) break;
    swapped = false;
    end--;
    for (let i = end; i > start; i--) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    start++;
  }
  return a;
}

// Приклад
console.log(bubbleSort([5, 1, 4, 2, 8]));            // [1, 2, 4, 5, 8]
console.log(bubbleSortOptimized([5, 1, 4, 2, 8]));   // [1, 2, 4, 5, 8]
console.log(cocktailShakerSort([5, 1, 4, 2, 8]));    // [1, 2, 4, 5, 8]

Складність і властивості

Час: O(n²) у середньому і найгіршому випадках; O(n) у найкращому (якщо масив уже відсортований і є ранній вихід).
Пам'ять: O(1) додаткової (in-place), якщо сортуємо вихідний масив.
Стійкість: стабільне сортування (зберігає відносний порядок рівних елементів).
Кількість порівнянь: ~n(n-1)/2 у найгіршому випадку; кількість обмінів - того самого порядку.

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

Використовувати: дуже малі масиви, майже відсортовані дані, освітні цілі, коли потрібна стабільність і простота реалізації.
Уникати: середні й великі обсяги даних - переважні алгоритми O(n log n) (наприклад, сортування злиттям, швидке, пірамідальне).

Оптимізації

Ранній вихід: якщо за прохід не було жодного обміну - завершуємо.
Межа останньої перестановки: після позиції останнього обміну хвіст уже відсортований - скорочуємо діапазон наступного проходу.
Двосторонній прохід (Cocktail Shaker): пришвидшує на майже відсортованих даних за рахунок переміщення великих елементів вправо і малих вліво за один цикл.

Часті помилки

Неправильні межі внутрішнього циклу (забувають -i, втрачають оптимізацію хвоста).
Відсутність раннього виходу - зайві проходи по вже відсортованому масиву.
Випадкові порушення стійкості під час спроби «пришвидшити» порівняння без потреби.

Коротке порівняння

Insertion Sort: також O(n²), але швидше за Bubble Sort на майже відсортованих даних і має менше операцій обміну.
Selection Sort: O(n²), але робить мінімум обмінів; нестійкий; зазвичай швидший за Bubble Sort за константами, але гірший на майже відсортованих даних.

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

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

Premium

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