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



             

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


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

x_1,x_2,\ldots,x_n
имеет вид

 x_i = (x_{i,p},x_{i,p - 1},\ldots,x_{i,1} )

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

 x_i = (x_{i,p},x_{i,p - 1},\ldots,x_{i,1} ) < (x_{j,p}^,,x_{j,p - 1},\ldots,x_{j,1} ) = x_j

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

t \leqslant p

имеем

x_{i,l} = x_{j,l}
для
l > t
и
x_{i,t} < x_{j,t}
. Для простоты будем считать, что
0 \leqslant x_{i,l} < r
, и поэтому имена можно рассматривать как целые, представленные по основанию
r
, так что каждое имя имеет
p
r
-ичных цифр. Более короткие имена дополняются нулями.




Содержание  Назад  Вперед