Поразрядная сортировка: подсчёт по цифрам

Если ты понимаешь, почему поразрядная сортировка идёт от младшей цифры к старшей, зачем ей устойчивость подсчёта и откуда берётся Θ(d·(n+b)), листай до «Теперь сам».

Как думаешь, как сортировать подсчётом большие числа

У подсчёта есть беда: при широком диапазоне значений массив счётчиков раздувается. Сортировать подсчётом числа до миллиарда нельзя - счётчиков был бы миллиард. Но у числа есть ЦИФРЫ, и каждая цифра - это маленький диапазон (для десятичных - всего 0..9). Напрашивается: сортировать не по всему числу сразу, а по цифрам по очереди, каждый раз дешёвым подсчётом с k = 10. Вопрос лишь в том, в каком ПОРЯДКЕ брать цифры и как не испортить уже наведённый порядок. Ответ - от младшей к старшей, опираясь на устойчивость.

На что это похоже

Старая картотека, которую надо разложить по номерам вида «сотни-десятки-единицы». Ты раскладываешь карточки на 10 стопок по ЕДИНИЦАМ и собираешь их по порядку стопок. Потом те же карточки раскладываешь по ДЕСЯТКАМ и снова собираешь. Наконец - по СОТНЯМ. Важно, что на каждом шаге, собирая стопки, ты не перемешиваешь карточки ВНУТРИ стопки - берёшь их в том порядке, в каком они легли. Тогда к концу карточки с одинаковой сотней уже упорядочены по десяткам и единицам из прошлых проходов. Три дешёвых раскладки по 10 стопок - и вся картотека в порядке.

Механизм: устойчивый подсчёт по цифрам от младшей к старшей

Пусть числа записаны в основании b (например, b = 10) и имеют d цифр. Повторяем d раз, начиная с МЛАДШЕЙ цифры (единицы), к старшей:

1. взять текущую цифру каждого числа (для десятичных - (x // разряд) % 10);
2. устойчиво отсортировать массив ПО ЭТОЙ ЦИФРЕ сортировкой подсчётом (k = b).

Устойчивость - обязательна: сортируя по очередной (более старшей) цифре, элементы с ОДИНАКОВОЙ текущей цифрой должны сохранить порядок, наведённый предыдущими (младшими) проходами. После d-го прохода (по старшей цифре) массив отсортирован полностью.

Правило

Поразрядная сортировка применяет УСТОЙЧИВУЮ сортировку подсчётом по одной цифре за раз, от МЛАДШЕЙ к старшей; после d проходов массив отсортирован. Устойчивость обязательна: она хранит порядок, наведённый младшими цифрами. Стоимость Θ(d·(n + b)), где d - число цифр, b - основание. Так подсчёт распространяют на большой диапазон значений: вместо одного огромного k - d дешёвых проходов с маленьким b.

Разбор: почему от младшей цифры к старшей, а не наоборот

Идти надо от МЛАДШЕЙ. Смысл: старшая цифра важнее младшей, поэтому она должна сортироваться ПОСЛЕДНЕЙ - тогда её порядок «главнее». А внутри одинаковой старшей цифры порядок задают младшие, отсортированные РАНЬШЕ и сохранённые устойчивостью. Проверим на 32, 15, 12, 25. По единицам: 32, 12, 15, 25 (цифры единиц 2,2,5,5; 32 и 12 сохранили взаимный порядок). По десяткам: 12, 15, 25, 32 (цифры десятков 1,1,2,3; 12 и 15 имели одинаковый десяток 1 и остались в порядке, наведённом единицами, - 12 перед 15). Готово. Если бы шли от СТАРШЕЙ, то следующая (младшая) сортировка перемешала бы уже наведённый старшей порядок - и всё сломалось бы. Направление «от младшей» плюс устойчивость - вот два условия корректности.

Разбор: когда поразрядная выигрывает у n·log n

Стоимость Θ(d·(n + b)). Если b фиксировано (скажем, 10 или 256), а число цифр d невелико и не растёт с n, то это Θ(d·n) = Θ(n) - линейно, быстрее n·log n. Например, сортировать n 32-битных целых можно за d = 4 прохода по байтам (b = 256): Θ(4·(n + 256)) = Θ(n). Выигрыш реален, когда элементов МНОГО, а ключи фиксированной, небольшой длины. Оговорка: d на самом деле связано с диапазоном значений (d ≈ log_b(макс)), так что для по-настоящему огромных или переменной длины ключей d растёт, и преимущество перед n·log n тает. Поразрядная - не всегда «бесплатная линия», а линия при небольшом фиксированном числе разрядов.

Что ломается без этого

Первая ошибка - использовать НЕустойчивую сортировку для прохода по цифре: тогда каждый следующий проход перемешивает порядок, наведённый предыдущими, и результат неверен. Устойчивость подсчёта здесь не украшение, а условие корректности. Вторая - идти от СТАРШЕЙ цифры к младшей в простом варианте (LSD, least significant digit - «от младшей цифры»): младшие проходы разрушат старший порядок. (Есть и MSD-вариант, most significant digit - «от старшей цифры», но он устроен иначе, рекурсивно по группам, и это отдельная история.) Третья - забыть, что d зависит от диапазона: на ключах переменной или огромной длины поразрядная теряет линейность.

Зачем это в работе

Поразрядная сортировка - способ отсортировать большие целочисленные ключи и строки фиксированной длины за линейное время: числовые идентификаторы, IP-адреса, даты как числа, строки одинаковой длины. Её используют в базах данных и системах обработки больших массивов чисел, где n огромно, а ключи - фиксированной битовой ширины: там Θ(n) поразрядной обгоняет Θ(n·log n) быстрой сортировки. Вместе с подсчётом она показывает главную мысль раздела: n·log n - предел только для СРАВНЕНИЙ, а зная структуру ключей (целые, цифры, байты), можно сортировать за линию. Выбор сортировки - это в первую очередь вопрос «что я знаю про свои ключи».

Теперь сам

Поразрядная сортировка обрабатывает 12 и 15 при проходе по ДЕСЯТКАМ. У обоих цифра десятков - 1. Почему после этого прохода 12 окажется раньше 15, хотя по десяткам они равны?