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

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

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

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

Контент

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

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

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

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

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

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

**Обмінні сортування (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, стабільна, з раннім виходом)

```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) - обмін при кожному порушенні порядку

```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)

```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.

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

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

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

Для рев’юера

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

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