Комбинаторные алгоритмы для программистов

         

Распределяющая сортировка


Обсуждаемый здесь алгоритм сортировки отличается от рассматривавшихся до сих пор тем, что он основан не на сравнениях между именами, а на представлении имен. Мы полагаем, что каждое из имен

имеет вид

и их нужно отсортировать в возрастающем лексикографическом порядке, то есть

тогда и только тогда, если для некоторого

имеем

для
и
. Для простоты будем считать, что
, и поэтому имена можно рассматривать как целые, представленные по основанию
, так что каждое имя имеет
-ичных цифр. Более короткие имена дополняются нулями.



Содержание раздела