Информатика · объяснение и практика

Поразрядная сортировка: зачем каждому проходу стабильность

LSD-сортировка по разрядам: проход от единиц к старшим цифрам, сохранение прежнего порядка и границы числовой модели.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

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

Один проход видит только одну цифру

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

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

Два прохода на четырёх числах

Для списка 42,17,12,47 проход по единицам даёт 42,12,17,47. Внутри группы с единицей 2 остаётся прежний порядок 42 перед 12; в группе с единицей 7 —17 перед 47. Теперь упорядочим десятки, не меняя взаимного порядка внутри новых групп.

В группу десятков 1 попадут 12 и 17 именно в таком порядке, а в группу десятков 4 —42 и 47. Получаем 12,17,42,47. Если второй проход произвольно поменяет местами 12 и 17, итог снова нарушит порядок по единицам внутри одной десятки. Поэтому стабильность каждого прохода является условием доказательства, а не косметическим свойством.

Пример

42,17,12,47 → по единицам 42,12,17,47 → по десяткам 12,17,42,47.

После второго стабильного прохода учтена пара цифр: десяток определяет старший порядок, а прежнее расположение сохраняет правильные единицы среди одинаковых десятков.

Где заканчивается простая модель

Для d разрядов и основания b каждый проход должен обработать n записей и организовать b групп, если используется прямое распределение. Оценка O(d(n+b)) показывает, откуда берутся затраты. Она не означает постоянного времени для числа с произвольно большим количеством цифр.

Отрицательные числа, переменная длина строк и языковой алфавит требуют дополнительных соглашений. Нельзя просто убрать минус или считать отсутствие символа обычной цифрой, не доказав сохранение нужного порядка. Перед применением определите допустимые ключи, их ширину и стабильный способ каждого распределения. Для произвольных строк это уже отдельная постановка задачи.

От чтения к действию

А теперь — вы

После стабильного прохода по единицам получен список [31, 21, 42, 12, 23, 33]. Каков результат следующего стабильного прохода по десяткам?

Частые вопросы

Почему нельзя начать с десятков тем же правилом и закончить единицами?

Тогда последний проход сделает единицы главным критерием и может разрушить порядок по десяткам. MSD-методы строятся иначе.

Ведущие нули меняют неотрицательное число?

Нет. Здесь они лишь выравнивают число разрядов для общей процедуры.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться