Що таке обмінні сортування (exchange sorts)?

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

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

Обмінні сортування (exchange sorts) - це клас алгоритмів, які впорядковують масив шляхом багаторазових обмінів (swap) пар елементів, що стоять у неправильному порядку. Вони засновані на порівняннях, зазвичай працюють in-place і включають такі алгоритми, як бульбашкова, шейкерна, непарно-парна, comb, gnome, а також підхід partition-exchange у швидкому сортуванні (quicksort).

Розгорнута відповідь

Визначення та ідея

Базова операція - обмін двох елементів місцями, коли виявлено, що вони порушують порядок.
Типовий процес - багаторазові проходи по масиву з попарними порівняннями та обмінами до повного впорядкування.
Це порівняльні сортування (comparison-based), часто in-place (потребують O(1) дод. пам'яті, не рахуючи стека рекурсії у quicksort).

Типові представники

Бульбашкова сортування (Bubble sort): міняє місцями сусідні елементи, стабільна, O(n²), з раннім виходом адаптивна до майже відсортованих даних (найкращий випадок O(n)).
Шейкерна (Cocktail shaker): двонаправлена версія бульбашкової, зменшує «застрягання» великих елементів на початку масиву.
Непарно-парна (Odd-Even sort): почергово порівнює пари (0,1), (2,3), … та (1,2), (3,4), …; добре паралелиться, але O(n²) послідовно.
Comb sort: обміни зі спадним «кроком» між парами, прискорює усунення «черепашачих» інверсій порівняно з бульбашковою; середня складність близько O(n²), але на практиці швидша за бульбашкову.
Gnome sort: «крокує» по масиву і повертається назад при кожному порушенні порядку, роблячи послідовності обмінів сусідів; близька до вставок за поведінкою, але реалізована через обміни.
Проста обмінна сортування O(n²) (часто так і називають Exchange sort): для кожного i порівнює з кожним j > i і негайно міняє місцями, якщо потрібно. Не стабільна через далекі обміни.
Швидка сортування (Quicksort): розділяй-і-володарюй з partition-exchange - перегруповує елементи навколо опорного за рахунок обмінів. Середня O(n log n), найгірша O(n²), зазвичай нестабільна.

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

Час: більшість простих обмінних - O(n²); покращення: бульбашкова з прапорцем - найкращий випадок O(n); quicksort - середній O(n log n), найгірший O(n²).
Пам'ять: як правило in-place (O(1)), виняток - стек рекурсії у quicksort (середній O(log n)).
Стабільність: бульбашкова - стабільна; проста exchange O(n²), comb, quicksort - зазвичай ні (якщо спеціально не модифікувати).
Адаптивність: бульбашкова/шейкерна - адаптивні до майже відсортованих даних; odd-even - зручна для паралелізму; quicksort - гарна кеш-локальність і відмінна практика.

Приклади коду

Бульбашкова сортування (JS, стабільна, з раннім виходом)

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

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

Проста обмінна сортування O(n²) (JS) - обмін при кожному порушенні порядку

function exchangeSort(arr, compare = (a, b) => a - b) {
  const a = arr; // сортуємо на місці
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (compare(a[i], a[j]) > 0) {
        // не сусідній обмін - алгоритм не стабільний
        [a[i], a[j]] = [a[j], a[i]];
      }
    }
  }
  return a;
}

// Приклад
const data2 = [3, 2, 1, 2];
console.log(exchangeSort(data2)); // [1, 2, 2, 3]

Швидка сортування (Quicksort, partition-exchange, JS)

function quickSort(arr, compare = (a, b) => a - b, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  const pivot = arr[right]; // Розбиття Ломуто для наочності
  let i = left;
  for (let j = left; j < right; j++) {
    if (compare(arr[j], pivot) <= 0) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; // обміни навколо опорного
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];

  quickSort(arr, compare, left, i - 1);
  quickSort(arr, compare, i + 1, right);
  return arr;
}

// Приклад
const data3 = [10, 7, 8, 9, 1, 5];
console.log(quickSort(data3)); // [1, 5, 7, 8, 9, 10]

Коли обирати обмінні сортування

Навчання і співбесіди: прості для пояснення, корисні для розуміння інверсій і стабільності.
Дуже малі масиви або майже відсортовані дані - бульбашкова з раннім виходом може бути прийнятною.
Потрібна in-place і проста реалізація - більшість обмінних не вимагають дод. пам'яті.
Для продуктивного коду зазвичай обирають quicksort (або гібрид/бібліотечні реалізації), а не O(n²) обмінні.

Порівняння з іншими класами сортувань

Вставками (Insertion): переносять елемент на потрібну позицію зсувами, а не обмінами; зазвичай кращі на майже відсортованих даних.
Вибором (Selection): шукають мінімум/максимум і роблять рідкісні обміни; фіксована кількість обмінів O(n), але все ще O(n²) порівнянь.
Злиттям (Merge): ділять і зливають з дод. пам'яттю, гарантують O(n log n) і стабільність.
Купою (Heap): використовують структуру даних «купа», O(n log n), in-place, але зазвичай нестабільні; менше обмінів, ніж у простих exchange.

Типові питання на співбесіді

Чому бульбашкова сортування стабільна, а проста exchange O(n²) - ні?
Як модифікувати бульбашкову для раннього виходу і яка від цього асимптотика в найкращому випадку?
Чому quicksort називають partition-exchange sort і чим він принципово відрізняється від O(n²) обмінних сортувань?
У яких випадках обмінні сортування доречні на практиці, а в яких - ні?

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

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

Premium

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