Сравнение алгоритмов сортировки
Единого самого быстрого алгоритма сортировки нет. Одни просты, но медленны, другие быстры на случайных данных, но спотыкаются на отсортированных, а третьи вообще не сравнивают значения. Гонка всех восьми на одном списке сразу показывает разницу.
Три семейства
Сортировки пузырьком, выбором и вставками — простые сортировки. Они сравнивают и меняют местами близко стоящие значения, и на случайном списке им нужно время, пропорциональное n². Сортировки слиянием, быстрая и пирамидальная умно делят работу, и им нужно время, пропорциональное n log n, — лучшее, чего может добиться сортировка, которой разрешено лишь спрашивать, какое из двух значений больше. Поразрядная сортировка и сортировка подсчётом совсем обходят этот вопрос: они используют сами цифры или значения, а это работает только для ключей вроде небольших целых чисел.
Как измерить работу
«Гонка сортировок» считает одну операцию за каждое сравнение, каждую прочитанную цифру или значение и каждый обмен или перемещение. На 40 случайных значениях получается около 120 у сортировки подсчётом, 240 у поразрядной, 260 у быстрой, 380 у сортировки слиянием, 490 у пирамидальной, около 820 у каждой из сортировок выбором и вставками и больше 1100 у сортировки пузырьком. Реальные компьютеры зависят и от памяти: на практике быстрая сортировка обычно быстрее, чем подсказывает её счётчик, а пирамидальная — медленнее, из-за того, как они проходят по списку.
Входные данные важны
На почти отсортированном списке сортировке вставками нужно всего около 50 операций для 40 значений, а сортировке пузырьком около 90, потому что каждое значение стоит рядом со своим местом. На обратном списке тем же двум нужно 1560 — это их худший случай. Сортировкам выбором, пирамидальной, слиянием, поразрядной и подсчётом порядок почти безразличен. Быстрая сортировка с медианой трёх хорошо справляется с отсортированными и обратными списками, но при наивном выборе опорного элемента отсортированный список для неё худший случай. Небольшое число разных значений замедляет быструю сортировку, потому что равные значения уходят в одну сторону.
Память и устойчивость
Сортировки пузырьком, выбором, вставками, быстрая и пирамидальная работают на месте, почти без дополнительной памяти. Сортировкам слиянием, поразрядной и подсчётом нужен буфер длиной со список. Устойчивая сортировка сохраняет исходный порядок равных значений: сортировки пузырьком, вставками, слиянием, поразрядная и подсчётом устойчивы, а выбором, быстрая и пирамидальная — нет. Устойчивость важна, когда вы сортируете записи сначала по одному полю, потом по другому.
Какую выбрать
На практике вы используете сортировку, встроенную в ваш язык программирования. Обычно это Timsort — сортировка слиянием, которая для коротких кусков использует сортировку вставками и быстро работает на частично отсортированных данных, или introsort — быстрая сортировка, которая при необходимости переходит на пирамидальную и использует сортировку вставками для маленьких частей. Для множества небольших целочисленных ключей сортировка подсчётом или поразрядная может обогнать обе. Сортировки пузырьком и выбором — в основном учебные инструменты.
Попробуйте сами
Откройте «Гонку сортировок» и нажмите «Пуск». Каждая дорожка — одна сортировка на одном и том же списке; число справа считает её операции, а дорожка становится зелёной, когда сортировка закончена. Попробуйте почти отсортированный список, обратный и список с небольшим числом разных значений и посмотрите, как меняется порядок финиша. У каждой сортировки есть и своё приложение, где её можно подробно пройти шаг за шагом.
Часто задаваемые вопросы
Какой алгоритм сортировки самый быстрый?
Для данных общего вида в среднем быстрее всех быстрая сортировка и сортировка слиянием (и гибриды на их основе, такие как introsort и Timsort): n log n. Для небольших целочисленных ключей сортировки подсчётом и поразрядная ещё быстрее. Для коротких или почти отсортированных списков побеждает сортировка вставками.
Почему ни одна сортировка сравнениями не может быть быстрее n log n?
Список из n значений может стоять в n! порядках, а у каждого сравнения два исхода, поэтому в худшем случае нужно не меньше log₂(n!) сравнений, чтобы различить их все. Это примерно n log₂ n. Поразрядная сортировка и сортировка подсчётом обходят это ограничение, потому что не сравнивают.
Какие алгоритмы сортировки устойчивы?
Сортировки пузырьком, вставками, слиянием, поразрядная и подсчётом устойчивы в своих обычных вариантах. Сортировка выбором, быстрая и пирамидальная — нет, потому что переносят значения на большие расстояния.
Каким сортировкам нужна дополнительная память?
Сортировкам слиянием, поразрядной и подсчётом нужен буфер примерно длиной со список. Сортировкам пузырьком, выбором, вставками и пирамидальной почти ничего не нужно, а быстрой — совсем немного для рекурсии.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Запустить гонку сортировок