Информатика · объяснение и практика
Поразрядная сортировка: зачем каждому проходу стабильность
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)) показывает, откуда берутся затраты. Она не означает постоянного времени для числа с произвольно большим количеством цифр.
Отрицательные числа, переменная длина строк и языковой алфавит требуют дополнительных соглашений. Нельзя просто убрать минус или считать отсутствие символа обычной цифрой, не доказав сохранение нужного порядка. Перед применением определите допустимые ключи, их ширину и стабильный способ каждого распределения. Для произвольных строк это уже отдельная постановка задачи.
От чтения к действию
А теперь — вы
Частые вопросы
Почему нельзя начать с десятков тем же правилом и закончить единицами?
Тогда последний проход сделает единицы главным критерием и может разрушить порядок по десяткам. MSD-методы строятся иначе.
Ведущие нули меняют неотрицательное число?
Нет. Здесь они лишь выравнивают число разрядов для общей процедуры.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сортировка подсчётом: диапазон значений важнее числа разрядов
Сортировка подсчётом: частоты целых ключей, сдвиг отрицательного диапазона и отличие числа значений от ширины диапазона.
Открыть темуСлияние отсортированных частей: два указателя и стабильность
Слияние двух готовых массивов: сравнение первых оставшихся элементов, обработка хвоста и правило стабильности при равенстве.
Открыть тему