- Сравниваются
- Отмечены (минимум, опорный элемент или ключ)
- Обменяны или перемещены
- На месте
| Место | Сортировка | Сравнения или чтения | Обмены или перемещения | Операции |
|---|
Гонка сортировок
Какой алгоритм сортировки самый быстрый? Это зависит от списка. «Гонка сортировок» запускает все восемь алгоритмов сортировки одновременно на одном и том же списке, каждый на своей дорожке, и считает каждое сравнение, чтение, обмен и перемещение одной операцией. Дорожки продвигаются по мере роста счётчиков, так что вы увидите, как эффективные сортировки финишируют, пока медленные ещё переставляют значения, и как меняется порядок финиша на почти отсортированном или обратном списке. Нажмите «Пуск», чтобы посмотреть гонку всех восьми алгоритмов сортировки на одном списке, или «Шаг» и «Назад», чтобы идти по одной операции. Перетащите ползунок, чтобы перейти в любое место. Каждое сравнение, чтение, обмен или перемещение считается одной операцией, и каждая дорожка продвигается по мере роста своего счётчика, поэтому сортировка, которой нужно меньше всего операций, финиширует первой. Выберите число столбиков и начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» и следите за восемью дорожками. «Шаг» и «Назад» двигают гонку на одну операцию; ползунок переходит в любое место гонки.
- Сравните таблицу результатов, затем попробуйте почти отсортированный и обратный список и посмотрите, как меняется расстановка мест.
Как устроена гонка
Все восемь сортировок получают один и тот же список. Каждое сравнение двух значений, каждая цифра или значение, прочитанные поразрядной сортировкой и сортировкой подсчётом, и каждый обмен или перемещение считаются одной операцией. В каждый момент гонки каждая дорожка показывает, как далеко продвинулась её сортировка за это число операций. Сортировка, которой нужно меньше операций, раньше доходит до конца. В таблице результатов для каждой сортировки указаны сравнения, обмены или перемещения и их сумма.
Что показывают результаты
На 40 случайных значениях сортировке подсчётом нужно около 120 операций, поразрядной около 240, быстрой около 260, а сортировке слиянием около 380. Следом идёт пирамидальная примерно с 490, сортировкам выбором и вставками нужно около 820, а сортировке пузырьком больше 1100. На почти отсортированном списке побеждает сортировка вставками примерно с 50 операциями, а сортировка пузырьком вторая. На обратном списке сортировкам пузырьком и вставками нужно по 1560. Сортировки подсчётом и поразрядная так часто побеждают, потому что эти значения — небольшие целые числа; для других данных их вообще нельзя применить.
Часто задаваемые вопросы
Какой алгоритм сортировки самый быстрый?
Это зависит от данных. Для небольших целых чисел меньше всего операций нужно сортировке подсчётом и поразрядной. Для данных общего вида на случайных списках быстрее всех быстрая сортировка и сортировка слиянием, а на почти отсортированных — сортировка вставками. Сортировки пузырьком и выбором медленные на всех списках, кроме самых маленьких.
Что считается операцией?
Каждое сравнение двух значений, каждая цифра или значение, прочитанные поразрядной сортировкой и сортировкой подсчётом, и каждый обмен или перемещение значения. Это простая модель: реальное время выполнения зависит ещё и от доступа к памяти и стоимости каждой операции.
Почему сортировки подсчётом и поразрядная так часто побеждают?
Потому что они никогда не сравнивают значения. Они пользуются тем, что значения — небольшие целые числа, поэтому их работа растёт как n плюс диапазон значений, а не как n log n. К данным, которые не состоят из небольших целых чисел, они неприменимы.
Почему сортировка вставками побеждает на почти отсортированном списке?
Потому что её работа равна числу значений плюс числу пар в неправильном порядке. В почти отсортированном списке таких пар очень мало, поэтому каждое значение сдвигается лишь на одно-два места.
Мои числа куда-нибудь отправляются?
Нет. Гонка идёт в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор