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

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

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

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

Контент

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

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

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

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

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

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

Для будь-яких універсальних порівняльних сортувань мінімально досяжна асимптотика - Θ(n log n) за кількістю порівнянь (у середньому і в найгіршому випадках). Швидше зробити не можна, тому що будь-яке порівняльне сортування повинно розрізнити n! перестановок, а бінарне дерево рішень вимагає щонайменше log2(n!) ≈ n log2 n - 1.44n порівнянь. Лінійний час O(n) можливий лише за додаткових обмежень на ключі (наприклад, цілі числа з обмеженого діапазону - counting/radix sort).

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

### Межі для порівняльних сортувань

- Нижня межа: будь-яке порівняльне сортування вимагає Ω(n log n) порівнянь.
- Верхня межа: існують алгоритми зі складністю O(n log n) - merge sort, heap sort (у найгіршому випадку), quicksort (у середньому випадку).
- Підсумок: оптимальна асимптотика для порівняльних алгоритмів - Θ(n log n). Основа логарифма не має значення (відрізняється константою).

### Інтуїція доведення через дерево рішень

1. Будь-яке порівняльне сортування - це послідовність запитань виду «a[i] ≤ a[j]?». Його роботу можна подати бінарним деревом рішень, де кожен вузол - порівняння, а лист - остаточний порядок.
2. Різних входів (перестановок) - n!, отже, листків не менше n!.
3. Бінарне дерево з L листками має глибину щонайменше log2 L, отже, глибина ≥ log2(n!). Це і є мінімальна кількість порівнянь у найгіршому випадку.
4. За формулою Стірлінга: log2(n!) ≈ n log2 n - 1.44n + O(log n). Отже, нижня межа - Ω(n log n).

### Передумови моделі (чому це справедливо)

- Ми рахуємо лише порівняння ключів; кожна операція порівняння дає не більше 1 біта інформації.
- Ключі довільні й неструктуровані (їх не можна «розкладати по кошиках» без порівнянь).
- Модель RAM з однаковою вартістю елементарних операцій.

### Коли можна швидше за O(n log n)

- Counting sort: O(n + k), де k - розмір діапазону цілих ключів. Вимагає, щоб ключі були невеликими цілими числами (наприклад, з [0, k)).
- Radix sort: O(n · d) за кількістю розрядів (або O(n log_k U) для основи k і діапазону U), працює для фіксованої довжини ключів/розрядів (рядки фіксованої довжини, 32/64-бітні цілі).
- Bucket sort: очікувано O(n) за «хорошого» розподілу даних (наприклад, рівномірного на [0,1)).
- Підсумок: лінійне сортування можливе, коли ми використовуємо структуру ключів (обмежений діапазон, фіксована довжина, припущення про розподіл). У загальному випадку без цих передумов - не можна.

### Практичні алгоритми та їхня складність

- Merge sort - O(n log n) у найгіршому випадку, стабільний, але вимагає O(n) дод. пам'яті.
- Heap sort - O(n log n) у найгіршому випадку, майже in-place, нестійкий, гірші константи/локальність.
- Quick sort - у середньому O(n log n), найгірший випадок O(n^2) (див. випадкові опорні елементи/median-of-three для зниження ризику), in-place, відмінна кеш-локальність.
- Timsort (у Python/Java) - найгірший випадок O(n log n), адаптивний: для майже відсортованих даних може бути близьким до O(n).

### Приклад коду: сортування O(n log n) (Merge Sort, JS)

```javascript
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);
    else res.push(b[j++]);
  }
  return res.concat(a.slice(i), b.slice(j));
}

// Приклад використання:
// const arr = [5, 1, 4, 2, 8];
// console.log(mergeSort(arr)); // [1, 2, 4, 5, 8]
```

### Приклад коду: O(n) за обмеженого діапазону (Counting Sort, JS)

```javascript
function countingSort(arr, min, max) {
  const k = max - min + 1;
  const count = new Array(k).fill(0);

for (const x of arr) {
    if (x < min || x > max) throw new Error('ключ поза діапазоном');
    count[x - min]++;
  }

let idx = 0;
  for (let i = 0; i < k; i++) {
    while (count[i]-- > 0) arr[idx++] = i + min;
  }
  return arr;
}

// Приклад використання:
// const arr = [5, 1, 4, 2, 8, 2];
// console.log(countingSort(arr, 0, 10)); // [1, 2, 2, 4, 5, 8]
// Важливо: працює ефективно, коли (max - min) = O(n).
```

### Підсумки

- Сортування загального призначення на основі порівнянь не може бути швидшим за Θ(n log n) - це інформаційно-теоретична нижня межа.
- Лінійні алгоритми сортування можливі лише за додаткових припущень про ключі або їхній розподіл.
- На практиці обирайте алгоритм під обмеження задачі: діапазон ключів, стабільність, пам'ять, розподіл даних.

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

Для рев’юера

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

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