Поразрядная сортировка
Поразрядная сортировка — белая ворона среди алгоритмов сортировки: она никогда не спрашивает, какое из двух значений больше. Она читает числа цифра за цифрой и сортирует их по одной цифре за раз, используя десять корзин. Идея старше компьютеров: так работали сортировальные машины для перфокарт.
Идея
Отсортируйте числа только по цифре единиц. Затем отсортируйте их по цифре десятков, но так, чтобы числа с одинаковой цифрой десятков остались в порядке, полученном на первом проходе. Затем по сотням, так же. После последнего прохода список отсортирован: сначала решают сотни, числа с одинаковыми сотнями уже упорядочены по десяткам, а с одинаковыми десятками — по единицам.
Один проход с корзинами
Каждый проход использует десять корзин, по одной на каждую цифру от 0 до 9. Пройдите по списку от начала до конца и перенесите каждое число в корзину его цифры, за числами, которые уже там лежат. Затем выложите корзины обратно в список по порядку, начиная с корзины 0. Именно перенос чисел в порядке списка и добавление их в конец корзины делает проход устойчивым. Приложение сначала подсчитывает числа для каждой цифры, чтобы корзины могли стоять рядом в одной строке, каждая сразу за предыдущей: это сортировка подсчётом по одной цифре.
Пример
Возьмём 170, 45, 75, 90, 802, 24, 2, 66. По цифре единиц: 170, 90, 802, 2, 24, 45, 75, 66. По цифре десятков: 802, 2, 24, 45, 66, 170, 75, 90; заметьте, что 802 и 2, у которых в разряде десятков 0, сохраняют свой порядок с первого прохода. По цифре сотен: 2, 24, 45, 66, 75, 90, 170, 802. Три прохода по восьми числам: прочитано 24 цифры, сделано 48 перемещений и ни одного сравнения.
Насколько она быстра?
Каждый проход читает одну цифру каждого числа и перемещает каждое число дважды, так что для n чисел с d цифрами работа растёт как n · d. Сортировке сравнением в худшем случае нужно не меньше примерно n log₂ n сравнений, потому что она должна различить n! возможных порядков, задавая по одному вопросу «да или нет». Поразрядная сортировка этим не ограничена, ведь она никогда не задаёт таких вопросов. Для множества коротких ключей, например миллиона чисел меньше 1000, три прохода — это гораздо меньше работы, чем примерно 20 миллионов сравнений, которые понадобились бы сортировке сравнением. Для длинных ключей или небольшого числа значений преимущество исчезает.
LSD и MSD, история
Показанный здесь вариант начинает с младшей цифры (LSD, least significant digit). Обратный способ, со старшей цифры (MSD, most significant digit), делит список на корзины по первой цифре и сортирует каждую корзину отдельно, что подходит для строк разной длины. Поразрядная сортировка восходит к сортировщикам перфокарт, появившимся после табуляторов, которые Герман Холлерит (Herman Hollerith) создал для переписи населения США 1890 года: сортировщик опускал каждую карту в один из десяти карманов по отверстию в одной колонке, а операторы пропускали колоду через машину по разу на каждую колонку, начиная с последней.
Попробуйте сами
Откройте приложение и нажмите «Шаг». Каждый проход сначала подсчитывает цифры, и это размечает корзины от 0 до 9 в строке под списком. Затем числа одно за другим падают в свои корзины (текущая корзина подсвечена) и копируются обратно. Введите свои числа до 999, например из примера выше, чтобы увидеть все три прохода.
Часто задаваемые вопросы
Какова временная сложность поразрядной сортировки?
O(n · d) для n ключей из d цифр в фиксированной системе счисления плюс затраты на корзины в каждом проходе. Ей нужно O(n) дополнительной памяти для буфера, в котором находятся корзины.
Устойчива ли поразрядная сортировка?
Поразрядная сортировка LSD обязана быть устойчивой: она работает только потому, что каждый проход оставляет значения с одинаковой цифрой в том порядке, в каком они пришли. Поэтому итоговый результат тоже устойчив.
Может ли поразрядная сортировка работать с отрицательными или дробными числами?
Не напрямую, но с помощью приёма может: сдвиньте отрицательные числа, чтобы все стали положительными, или отсортируйте их отдельно и разверните. Числа с плавающей точкой можно сортировать по их битовому представлению после небольшого преобразования.
Почему основание 10?
Потому что за ним легко следить. Компьютеры обычно сортируют по 8 или 16 бит за раз, так что 32-битному числу нужно четыре или два прохода с 256 или 65 536 корзинами.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать поразрядную сортировку