Що таке сортування?
Що таке сортування?
Коротка відповідь
Сортування - це процес впорядкування елементів колекції (масивів, списків) за заданим ключем або правилом порівняння. Це дає змогу швидше шукати, агрегувати й обробляти дані. Ефективні порівняльні алгоритми сортують за 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).
Часто вживані алгоритми
- Вставками (Insertion Sort): O(n^2) у середньому і найгіршому, O(n) у найкращому (майже відсортовано); пам'ять O(1); стабільний; in-place. Добрий при n ≤ ~50-200 або майже відсортованих даних.
- Злиттям (Merge Sort): O(n log n) завжди; пам'ять O(n); стабільний; out-of-place. Добрий для великих даних, коли потрібна стабільність, для зовнішнього сортування і зв'язних списків.
- Швидка (Quick Sort): середнє O(n log n), найгірше O(n^2); пам'ять O(log n) за рахунок рекурсії; нестабільний; in-place. Часто найшвидша на практиці за хорошого вибору опорного елемента й оптимізацій.
- Пірамідальна (Heap Sort): O(n log n) у середньому/найгіршому; пам'ять O(1); нестабільний; in-place. Передбачувана найгірша складність без дод. пам'яті.
- Підрахунком (Counting Sort): O(n + k); пам'ять O(n + k); стабільний за коректної реалізації; out-of-place. Працює для цілих ключів обмеженого діапазону k.
- Порозрядна (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 для цілочислових діапазонів. У прикладному коді особливо важливо коректно задавати компаратор і враховувати локаль/тип ключів.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.