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

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

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

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

Контент

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

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

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

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

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

## Що таке сортування?

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

**Сортування** - це процес впорядкування елементів колекції (масивів, списків) за заданим ключем або правилом порівняння. Це дає змогу швидше шукати, агрегувати й обробляти дані. Ефективні порівняльні алгоритми сортують за O(n log n), а вибір конкретного алгоритму залежить від вимог до стабільності, пам'яті й розміру даних.

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

#### Ключові цілі та терміни

- Призначення: впорядкувати елементи за ключем (число, рядок, дата, складений ключ) для пришвидшення пошуку, об'єднання й аналітики.
- Стабільність: стабільне сортування зберігає вихідний відносний порядок елементів з рівними ключами.
- In-place vs out-of-place: in-place використовує O(1) додаткової пам'яті (окрім стека), out-of-place вимагає дод. масиви.
- Внутрішня vs зовнішня: внутрішня (in-memory) працює в ОЗП; зовнішня (external) - при даних, що не вміщуються в пам'ять (файли, потоки), зазвичай на основі сортування злиттям з багатошляховим злиттям.
- Порівняльна vs непорівняльна: порівняльна використовує лише порівняння (нижня межа Ω(n log n)); непорівняльна (підрахунком, порозрядна) вимагає додаткові передумови про ключі і може бути швидшою - O(n + k).

#### Часто вживані алгоритми

1. Вставками (Insertion Sort): O(n^2) у середньому і найгіршому, O(n) у найкращому (майже відсортовано); пам'ять O(1); стабільний; in-place. Добрий при n ≤ ~50-200 або майже відсортованих даних.
2. Злиттям (Merge Sort): O(n log n) завжди; пам'ять O(n); стабільний; out-of-place. Добрий для великих даних, коли потрібна стабільність, для зовнішнього сортування і зв'язних списків.
3. Швидка (Quick Sort): середнє O(n log n), найгірше O(n^2); пам'ять O(log n) за рахунок рекурсії; нестабільний; in-place. Часто найшвидша на практиці за хорошого вибору опорного елемента й оптимізацій.
4. Пірамідальна (Heap Sort): O(n log n) у середньому/найгіршому; пам'ять O(1); нестабільний; in-place. Передбачувана найгірша складність без дод. пам'яті.
5. Підрахунком (Counting Sort): O(n + k); пам'ять O(n + k); стабільний за коректної реалізації; out-of-place. Працює для цілих ключів обмеженого діапазону k.
6. Порозрядна (Radix Sort): O(d·(n + b)), де d - кількість розрядів, b - основа; пам'ять O(n + b); зазвичай стабільний; out-of-place. Для чисел/рядків фіксованого формату.

#### Вибір алгоритму на практиці

- Потрібна стабільність: Merge Sort/Timsort/Counting/Radix.
- Мінімум пам'яті: Quick Sort (in-place) або Heap Sort.
- Майже відсортовані дані: Insertion Sort або гібрид (наприклад, Timsort).
- Обмежений діапазон цілих ключів: Counting/Radix (дуже швидко).
- Дуже великі дані поза пам'яттю: зовнішнє сортування (багатошляхове злиття).

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

#### JavaScript: сортування з компаратором (стабільно за полем)

Важливе правило: компаратор повинен повертати від'ємне/нуль/додатне число, а не true/false.

```js
const users = [
  { name: 'Maria', age: 25 },
  { name: 'Oleh', age: 20 },
  { name: 'Bob', age: 25 },
  { name: 'Alice', age: 20 }
];

// Спочатку за age за зростанням, потім за name з урахуванням локалі (стабільно)
users.sort((a, b) => {
  if (a.age !== b.age) return a.age - b.age;
  return a.name.localeCompare(b.name, 'en');
});

const nums = [10, 2, 3, 1];
// Правильно: числова сортування
nums.sort((a, b) => a - b);

// Неправильно: повертає true/false, що може дати некоректний порядок
// nums.sort((a, b) => a < b);

// Примітка: сучасні реалізації JS (ES2019+) роблять Array.prototype.sort стабільним.
```

#### Швидке сортування (QuickSort) in-place

```js
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;
  const pivot = arr[(left + right) >> 1];
  let i = left, j = right;
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++; j--;
    }
  }
  if (left < j) quickSort(arr, left, j);
  if (i < right) quickSort(arr, i, right);
  return arr;
}

console.log(quickSort([3, 6, 1, 5, 2, 4]));
```

#### Сортування злиттям (MergeSort) - стабільна

```js
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));
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      res.push(left[i++]);
    } else {
      res.push(right[j++]);
    }
  }
  return res.concat(left.slice(i), right.slice(j));
}

console.log(mergeSort([5, 2, 4, 6, 1, 3]));
```

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

- Компаратор повертає true/false, а не число (JS). Повинно бути: a - b або localeCompare.
- Ігнорування локалі під час порівняння рядків: регістр, діакритичні знаки, числова сортування рядків ('10' < '2'). Використовуйте localeCompare або попередню нормалізацію.
- Вибір O(n^2) алгоритмів на великих даних без потреби (Bubble/Selection/Insertion на невідсортованих масивах).
- Непродумана пам'ять: Merge Sort вимагає O(n) додаткової пам'яті; для дуже великих масивів використовуйте зовнішнє злиття або in-place підходи.
- Відсутність стабільності там, де важливий вихідний порядок рівних ключів (наприклад, багатокритеріальне сортування).
- Поганий вибір опорного елемента в QuickSort може призвести до O(n^2). Використовуйте медіану трьох, випадковий pivot або гібридизацію.

### Коротка пам'ятка щодо складності

| Алгоритм | Середня | Найгірша | Пам'ять | Стабільна | In-place |
|---|---|---|---|---|---|
| Бульбашкова | O(n^2) | O(n^2) | O(1) | Так | Так |
| Вставками | O(n^2) | O(n^2) | O(1) | Так | Так |
| Вибором | O(n^2) | O(n^2) | O(1) | Ні | Так |
| Злиттям | O(n log n) | O(n log n) | O(n) | Так | Ні |
| Швидка (Quick) | O(n log n) | O(n^2) | O(log n) | Ні | Так |
| Пірамідальна (Heap) | O(n log n) | O(n log n) | O(1) | Ні (зазвичай) | Так |
| Підрахунком (Counting) | O(n + k) | O(n + k) | O(n + k) | Так (якщо робити префіксні суми) | Ні |
| Порозрядна (Radix) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Зазвичай так | Ні |

### Підсумок

Сортування - базовий інструмент для роботи з даними. Розуміння стабільності, асимптотик, вимог до пам'яті й природи ключів допомагає усвідомлено обирати алгоритм: Timsort/Merge для стабільності, Quick/Heap для in-place, Counting/Radix для цілочислових діапазонів. У прикладному коді особливо важливо коректно задавати компаратор і враховувати локаль/тип ключів.

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

Для рев’юера

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

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