Алгоритм сортировки упорядочивает элементы коллекции. QuickSort и MergeSort делают это за O(n log n); простые алгоритмы вроде BubbleSort — за O(n²), что на больших данных в тысячи раз медленнее.
💻Sorting Algorithms
From basic methods to fast algorithms (QuickSort, TimSort). Ordering elements is one of the key tasks
Article body and graph labels may still appear in Russian where English translations have not been added yet.
Loading map...
Зачем сортировать и почему это сложно
Поиск в отсортированном массиве занимает O(log n) — это двоичный поиск. В неотсортированном — O(n), то есть просматривать каждый элемент. Разница между log(1 000 000) = 20 и 1 000 000 операций огромна. Поэтому сортировка — фундамент алгоритмики.
Сложность в том, что разные алгоритмы лучше работают в разных условиях: маленький массив, почти отсортированный, много повторений, ограничена память. Универсального лучшего алгоритма нет.
Простые алгоритмы — медленные, но понятные
Bubble Sort — сравниваем соседние элементы и меняем местами, если стоят не так. Повторяем, пока массив не отсортирован. O(n²). Для 10 000 элементов — 100 миллионов сравнений. Почти никогда не используется в реальности.
Insertion Sort — берём элемент и вставляем его на правильное место в уже отсортированную часть. Как сортируют карты в руке. O(n²) в худшем случае, но O(n) на почти отсортированном массиве. Используется внутри TimSort для маленьких кусков.
Selection Sort — находим минимум, ставим первым, находим следующий минимум, ставим вторым. O(n²) всегда. Простой, но неэффективный.
Сравнение алгоритмов сортировки
| Алгоритм | Среднее | Худшее | Память | Стабильный |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Да |
| Insertion Sort | O(n²) | O(n²) | O(1) | Да |
| Selection Sort | O(n²) | O(n²) | O(1) | Нет |
| QuickSort | O(n log n) | O(n²) | O(log n) | Нет |
| MergeSort | O(n log n) | O(n log n) | O(n) | Да |
| HeapSort | O(n log n) | O(n log n) | O(1) | Нет |
| Counting Sort | O(n+k) | O(n+k) | O(k) | Да |
| TimSort | O(n log n) | O(n log n) | O(n) | Да |
Сравнительная таблица: анализ различий
Быстрые алгоритмы — O(n log n)
QuickSort (1959, Тони Хоар) — выбираем опорный элемент (pivot), разделяем массив на «меньше pivot» и «больше pivot», рекурсивно сортируем каждую часть. В среднем O(n log n), в худшем — O(n²). На практике самый быстрый для случайных данных.
MergeSort — делим массив пополам, сортируем каждую половину, сливаем. Всегда O(n log n). Стабильный — одинаковые элементы сохраняют порядок. Требует дополнительную память O(n). Хорош для связных списков и внешней сортировки.
HeapSort — строим кучу (heap), затем последовательно извлекаем максимум. Всегда O(n log n), O(1) дополнительной памяти. Но на практике медленнее QuickSort из-за плохой кэш-локальности.
Специальные алгоритмы
Counting Sort — подсчитываем количество каждого значения, затем выстраиваем. O(n + k), где k — диапазон значений. Идеален для сортировки оценок (1–5), возрастов (0–120). Не работает для вещественных чисел.
TimSort — гибрид MergeSort и Insertion Sort. Делит массив на «runs» (уже отсортированные куски), сортирует маленькие части Insertion Sort, сливает MergeSort. O(n log n) в худшем, O(n) для почти отсортированных. Стандартный алгоритм в Python (sorted()) и Java (Arrays.sort()).
Операции для сортировки 10000 элементов (приблизительно)
Операций (млн)
Как выбрать алгоритм
Маленький массив (<50 элементов) — Insertion Sort. Случайные данные — QuickSort. Нужна стабильность — MergeSort. Почти отсортированный массив — TimSort или Insertion Sort. Целые числа в маленьком диапазоне — Counting Sort.
❓Часто задаваемые вопросы
На практике худший случай редок, а константа у QuickSort маленькая — поэтому он быстрее MergeSort на реальных данных.