Выбор алгоритма сортировки
Итоговое сравнение
| Алгоритм | Время (среднее) | Время (худшее) | Память | Стабильная | Когда использовать |
|---|---|---|---|---|---|
| Insertion Sort | O(n²) | O(n²) | O(1) | ✓ | n < 20, почти отсортированные |
| QuickSort | O(n log n) | O(n²) | O(log n) | ✗ | Общий случай, in-place |
| MergeSort | O(n log n) | O(n log n) | O(n) | ✓ | Нужна стабильность, linked list |
| HeapSort | O(n log n) | O(n log n) | O(1) | ✗ | Гарантия + O(1) памяти |
| sort.Slice (Go) | O(n log n) | O(n log n) | O(log n) | ✗ | Практика — всегда |
Практические правила
Используй sort.Slice — реализация Go (паттерн pdqsort) быстра на реальных данных.
Нужна стабильность — sort.SliceStable или MergeSort.
Малые данные (n < 20) — Insertion Sort быстрее из-за отсутствия накладных расходов.
Гарантированное O(n log n) без доп. памяти — HeapSort (редкий случай).
Частично отсортированные данные — Insertion Sort (O(n) на полностью отсортированных).
Внутренняя реализация sort.Slice в Go
Go использует pdqsort (pattern-defeating quicksort) — гибрид:
- QuickSort с медианой трёх для pivot
- Insertion Sort для малых подмассивов (< 12 элементов)
- HeapSort при деградации QuickSort
Это даёт O(n log n) на всех практических данных.
Упражнения
| № | Задание | Сложность |
|---|---|---|
| 1 | Упражнение 1 | easy |
| 2 | Упражнение 2 | easy |
| 3 | Упражнение 3 | medium |