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

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

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

$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$

-ичных цифр. Более короткие имена дополняются нулями.

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