- Текущая корзина
- Только что перемещён
- Скопированы обратно
- На месте
Поразрядная сортировка
Поразрядная сортировка упорядочивает целые числа, ни разу не сравнивая два из них. Она сортирует список по цифре единиц, затем по цифре десятков, затем сотен, каждый раз перенося значения в десять корзин и копируя их обратно по порядку. Смотрите, как корзины в строке под списком заполняются по одному перемещению, а список становится отсортированным по всё большему числу цифр. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному перемещению. Перетащите ползунок шагов, чтобы перейти в любое место. Корзины от 0 до 9 стоят рядом в строке под списком. Плитки считают прочитанные цифры, перемещения и проходы. Выберите число столбиков, начальный порядок или введите свои числа до 999. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок или введите свои целые числа до 999, чтобы увидеть проход по сотням.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы переносить по одному значению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Следите за каждым проходом: подсчёт цифр, перенос каждого значения в его корзину, затем копирование корзин обратно.
Как работает поразрядная сортировка
Посмотрите только на последнюю цифру каждого числа и отсортируйте список по ней: положите каждое число в одну из десяти корзин, от 0 до 9, в том порядке, в каком числа идут, затем скопируйте корзины обратно одну за другой. То же самое сделайте с цифрой десятков, затем с цифрой сотен. Поскольку каждый проход сохраняет порядок чисел с одинаковой цифрой, более ранние проходы по-прежнему определяют порядок между ними, и после последнего прохода весь список отсортирован.
Никаких сравнений
Сортировкам сравнением в худшем случае нужно не меньше примерно n log₂ n сравнений, какой бы хитрый приём они ни использовали. Поразрядная сортировка обходит этот предел, читая вместо этого цифры: каждый проход читает одну цифру каждого значения и перемещает каждое значение дважды, так что d цифр требуют d проходов, а работа растёт как n · d. Для длинных списков коротких ключей это окупается: миллион чисел до 999 требует трёх проходов, тогда как сортировке сравнением нужно около 20 миллионов сравнений. Цена в том, что она работает только для ключей из цифр или символов и ей нужно место для корзин.
Часто задаваемые вопросы
Как работает поразрядная сортировка?
Она сортирует числа по последней цифре, затем по цифре перед ней и так далее до первой цифры. Каждый проход раскладывает числа по десяти корзинам по этой цифре, сохраняя их порядок, и копирует корзины обратно. После прохода по старшей цифре список отсортирован.
Почему начинать с последней цифры?
Потому что каждый проход устойчив: числа с одинаковой цифрой сохраняют порядок, который дали им предыдущие проходы. Поэтому последний проход, по первой цифре, определяет порядок, а при равенстве решают уже отсортированные цифры. Это называется поразрядной сортировкой LSD (least significant digit, с младшего разряда).
Поразрядная сортировка быстрее быстрой сортировки?
Может быть, если коротких ключей много: её работа растёт как число значений, умноженное на число цифр, без n log n. Для небольшого числа значений, очень длинных ключей или данных, которые не состоят из цифр, быстрая сортировка и сортировка слиянием обычно быстрее и проще.
Как она связана с сортировкой подсчётом?
Каждый проход поразрядной сортировки — это сортировка подсчётом по одной цифре: подсчитать, сколько значений с каждой цифрой, вычислить, где начинается каждая корзина, и перенести туда значения по порядку.
Мои числа куда-то отправляются?
Нет. Сортировка выполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор