Победитель
Операции
Завершили

  • Сравниваются
  • Отмечены (минимум, опорный элемент или ключ)
  • Обменяны или перемещены
  • На месте
Место Сортировка Сравнения или чтения Обмены или перемещения Операции

Подробнее об алгоритмах сортировки

Гонка сортировок

Какой алгоритм сортировки самый быстрый? Это зависит от списка. «Гонка сортировок» запускает все восемь алгоритмов сортировки одновременно на одном и том же списке, каждый на своей дорожке, и считает каждое сравнение, чтение, обмен и перемещение одной операцией. Дорожки продвигаются по мере роста счётчиков, так что вы увидите, как эффективные сортировки финишируют, пока медленные ещё переставляют значения, и как меняется порядок финиша на почти отсортированном или обратном списке. Нажмите «Пуск», чтобы посмотреть гонку всех восьми алгоритмов сортировки на одном списке, или «Шаг» и «Назад», чтобы идти по одной операции. Перетащите ползунок, чтобы перейти в любое место. Каждое сравнение, чтение, обмен или перемещение считается одной операцией, и каждая дорожка продвигается по мере роста своего счётчика, поэтому сортировка, которой нужно меньше всего операций, финиширует первой. Выберите число столбиков и начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
  2. Нажмите «Пуск» и следите за восемью дорожками. «Шаг» и «Назад» двигают гонку на одну операцию; ползунок переходит в любое место гонки.
  3. Сравните таблицу результатов, затем попробуйте почти отсортированный и обратный список и посмотрите, как меняется расстановка мест.

Как устроена гонка

Все восемь сортировок получают один и тот же список. Каждое сравнение двух значений, каждая цифра или значение, прочитанные поразрядной сортировкой и сортировкой подсчётом, и каждый обмен или перемещение считаются одной операцией. В каждый момент гонки каждая дорожка показывает, как далеко продвинулась её сортировка за это число операций. Сортировка, которой нужно меньше операций, раньше доходит до конца. В таблице результатов для каждой сортировки указаны сравнения, обмены или перемещения и их сумма.

Что показывают результаты

На 40 случайных значениях сортировке подсчётом нужно около 120 операций, поразрядной около 240, быстрой около 260, а сортировке слиянием около 380. Следом идёт пирамидальная примерно с 490, сортировкам выбором и вставками нужно около 820, а сортировке пузырьком больше 1100. На почти отсортированном списке побеждает сортировка вставками примерно с 50 операциями, а сортировка пузырьком вторая. На обратном списке сортировкам пузырьком и вставками нужно по 1560. Сортировки подсчётом и поразрядная так часто побеждают, потому что эти значения — небольшие целые числа; для других данных их вообще нельзя применить.

Часто задаваемые вопросы

Какой алгоритм сортировки самый быстрый?

Это зависит от данных. Для небольших целых чисел меньше всего операций нужно сортировке подсчётом и поразрядной. Для данных общего вида на случайных списках быстрее всех быстрая сортировка и сортировка слиянием, а на почти отсортированных — сортировка вставками. Сортировки пузырьком и выбором медленные на всех списках, кроме самых маленьких.

Что считается операцией?

Каждое сравнение двух значений, каждая цифра или значение, прочитанные поразрядной сортировкой и сортировкой подсчётом, и каждый обмен или перемещение значения. Это простая модель: реальное время выполнения зависит ещё и от доступа к памяти и стоимости каждой операции.

Почему сортировки подсчётом и поразрядная так часто побеждают?

Потому что они никогда не сравнивают значения. Они пользуются тем, что значения — небольшие целые числа, поэтому их работа растёт как n плюс диапазон значений, а не как n log n. К данным, которые не состоят из небольших целых чисел, они неприменимы.

Почему сортировка вставками побеждает на почти отсортированном списке?

Потому что её работа равна числу значений плюс числу пар в неправильном порядке. В почти отсортированном списке таких пар очень мало, поэтому каждое значение сдвигается лишь на одно-два места.

Мои числа куда-нибудь отправляются?

Нет. Гонка идёт в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор