Сравнение алгоритмов сортировки: время, память и устойчивость
Сравнение алгоритмов сортировки в сводной таблице
Ниже представлены основные характеристики разобранных нами сортировок. Простые алгоритмы (с квадратичной сложностью) годятся только для учебных целей и малых наборов данных, тогда как для серьезных задач используются эффективные сортировки с логарифмическим фактором.
| Алгоритм | Лучшее время | Среднее время | Худшее время | Доп. память | Устойчивая |
|---|---|---|---|---|---|
| Сортировка вставкой | O(N) | O(N²) | O(N²) | O(1) | Да |
| Сортировка выборкой | O(N²) | O(N²) | O(N²) | O(1) | Нет |
| Пузырьковая сортировка | O(N) | O(N²) | O(N²) | O(1) | Да |
| Сортировка Шелла | O(N log N) | O(N1.3) | O(N²) | O(1) | Нет |
| Турнирная сортировка | O(N log N) | O(N log N) | O(N log N) | O(N) | Нет |
| Пирамидальная сортировка | O(N log N) | O(N log N) | O(N log N) | O(1) | Нет |
| Быстрая сортировка Хоара | O(N log N) | O(N log N) | O(N²) | O(log N) | Нет |
| Сортировка слиянием | O(N log N) | O(N log N) | O(N log N) | O(N) | Да |
| Сортировка естественным слиянием | O(N) | O(N log N) | O(N log N) | O(N) | Да |
| Сортировка Timsort | O(N) | O(N log N) | O(N log N) | O(N) | Да |
| Сортировка подсчетом | O(N+K) | O(N+K) | O(N+K) | O(K) | Да |
| Поразрядная сортировка | O(D(N+K)) | O(D(N+K)) | O(D(N+K)) | O(N+K) | Да |
| Карманная сортировка | O(N+K) | O(N+K) | O(N²) | O(N+K) | Да |
- N - количество элементов в массиве.
- K - диапазон возможных значений элементов (или основание системы счисления).
- D - количество разрядов в самом длинном ключе.
- Устойчивая (Stable) - сортировка не меняет исходный порядок равных элементов (критически важно при многоуровневой сортировке, например, сначала по имени, затем по возрасту).
- Доп. память O(1) - алгоритм работает на месте (in-place), обходясь константным числом дополнительных переменных.
Изучайте механику алгоритмов по шагам
Фундаментальное ограничение: теорема о нижней границе
Анализируя таблицу, можно заметить, что ни одна из сортировок, основанных на попарных сравнениях (Хоара, Слиянием, Пирамидальная), не работает быстрее O(N log N). Это не совпадение и не недостаток реализации, а математически доказанный факт.
Любой алгоритм, сортирующий элементы только путем их сравнения между собой, можно представить в виде дерева решений. Поскольку существует N! (факториал) возможных перестановок элементов, минимальная высота такого дерева (которая и определяет количество сравнений в худшем случае) составляет
log₂(N!) ≈ N log N.
Обмануть эту границу можно только отказавшись от прямых сравнений. Именно это делают Сортировка подсчетом и Поразрядная сортировка - они опираются на внутреннюю структуру ключей (цифры, разряды) и их диапазон, что позволяет достичь линейного времени O(N).
Практические выводы: что выбрать?
Идеальной сортировки на все случаи жизни не существует. Выбор зависит от входных данных и ограничений системы:
- Если данных мало (N ≤ 50): используйте Сортировку вставкой. Она отличается минимальными накладными расходами, работает без выделения дополнительной памяти и является устойчивой. Именно поэтому в стандартных библиотеках языков программирования гибридные алгоритмы (Timsort, Introsort) переключаются на вставку для коротких подмассивов.
- Если нужна максимальная скорость для случайных данных: выбирайте Быструю сортировку Хоара. Благодаря высокой кэш-локальности, она опережает конкурентов с аналогичной асимптотикой O(N log N). Главный недостаток - риск деградации до O(N²) при неудачном выборе опорного элемента и отсутствие устойчивости.
- Если важна гарантированная производительность и устойчивость: идеальный выбор - Сортировка слиянием или ее продвинутые варианты: Естественное слияние и Timsort. Эти алгоритмы не склонны к деградации и всегда работают за время O(N log N). Главный недостаток - необходимость выделения O(N) дополнительной памяти под буферный массив.
- Если доступная память жестко ограничена, но требуется скорость: ваш вариант - Пирамидальная сортировка (Heap Sort). Она выполняется прямо на месте (O(1) доп. памяти) и гарантирует время работы O(N log N). К сожалению, на практике она уступает Быстрой сортировке из-за постоянных прыжков по памяти.
- Если сортируемые ключи лежат в узком диапазоне: применяйте Сортировку подсчетом. Она работает за гарантированное линейное время O(N).
Коротко: главное
- Сортировки слиянием (включая Timsort) и пирамидальная гарантируют время O(N log N) в любом случае.
- Математически доказано, что сортировки, основанные только на сравнениях, не могут работать быстрее O(N log N).
- Сортировка Хоара обгоняет другие за счет работы с кэшем процессора, но имеет худший случай O(N²).
- Для преодоления барьера O(N log N) алгоритм должен использовать внутреннюю структуру данных, как это делают сортировки подсчетом и поразрядная.
- На малых массивах (N ≤ 50) эффективнее всего применять простые алгоритмы с малой константой, например, сортировку вставкой.
Проверьте себя: Вопрос 1
Вам нужно отсортировать базу из 10 000 000 записей о возрасте пользователей сайта (целые числа от 0 до 150). Устойчивость важна. Какой алгоритм подойдет лучше всего?
Вопрос 2
Вы программируете микроконтроллер для медицинского прибора. ОЗУ крайне мало, поэтому выделять O(N) дополнительной памяти под массивы нельзя. Кроме того, задержки недопустимы - алгоритм обязан всегда отрабатывать за O(N log N). Что выберете?
Вопрос 3
У вас есть огромный лог-файл событий сервера, который уже отсортирован по времени. Из-за сбоя сети несколько последних событий записались не по порядку. Какая сортировка быстрее всего вернет логу идеальный порядок?