Количество операций анализа отдельных разрядов - 82 - также велико, но мы увидим, что число такого типа операций при больших N в действительности меньше, чем число сравнений при быстрой сортировке, в предположении, что значения ключей имеют равномерное распределение. Общее количество обменов записей в табл. 3 равно 17, т. е. оно весьма умеренно. Заметим, что, хотя сортируются 10-битовые числа, в данном примере при проверке битов никогда не приходится идти дальше седьмого бита.

Как и при быстрой сортировке, для хранения "информации о границах" подмассивов, ожидающих сортировки, можно воспользоваться стеком. Вместо того чтобы сортировать, в первую очередь, наименьший из подмассивов, удобно просто продвигаться слева направо, и размер стека в этом случае никогда не превзойдет числа разрядов в двоичном представлении сортируемых ключей. В алгоритме, приведенном ниже, элемент стека (г, 6) урсазывает на то, что подмассив с правой границей г ожидает сортировки по Ь-му разряду; левую гргьницу можно не запоминать в стеке: она всегда задана неявно, поскольку в этой процедуре массив всегда обрабатьшается слева направо.

Алгоритм R (Обменная поразрядная сортировка). Записи Ri,..., R перекомпоновываются в пределах той же области памяти. По завершении сортировки их ключи будут упорядочены: К\<- <Kn- Предполагается, что все ключи - тп-разрядные двоичные числа (ai 02... ат)2; г-й по старшинству разряд Oj назьшается "разряд г" ключа. Необходим вcпo!Oгaтeльный стек, вмещающий до m - 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями, описанной выше. Возможны некоторые усовершенствования с целью повышения эффективности (они описаны ниже, в тексте раздела и в упражнениях).

R1. [Начальная установка.] Очистить стек и установить I -h- 1, г <- N, b -h- 1.

R2. [Начать новую итерацию.] (Теперь желательно рассортировать подмассив Ri Rr по разряду Ь в соответствии с алгоритмом I < г.) Если I = г, перейти к шагу R10 (так как массив, состоящий из одного слова, уже рассортирован). В противном, случае установить i <- I, j <- г.

КЗ. [Проверить наличие 1 в Ki.] Проверить разряд b ключа Ki. Если он равен 1, то перейти к шагу R6.

R4. [Увеличить г.] Увеличить г на 1. Если г < j, возвратиться к шагу R3; в противном случае перейти к шагу R8.

R5. [Проверить наличие О в Kj+i.] Проверить разряд b ключа Kj+i. Если он равен О, то перейти к шагу R7.

R6. [Уменьшить j.] Уменьшить j на 1. Если г < j, перейти к шагу R5; в противном случае перейти к шагу R8.

R7. [Поменять местами Ri, Rj+i.] Поменять местами записи Ri 4-> Rj+i и перейти к шагу R4.

R8. [Проверить особые случаи.] (К этому моменту итерация разделения завершена, i = j + l, разряд b ключей Ki,... ,Kj равен О, а разряд b ключей К,... ,Кг равен 1.) Увеличить b на 1. Если b > т, где ш - общее число разрядов в ключах, перейти к шагу R10. (Это означает, что подмассив Ri.. .R рассортирован. Если в массиве не может быть равных ключей, то такую проверку

Таблица 3

ОБМЕННАЯ ПОРАЗРЯДНАЯ СОРТИРОВКА

Итерация

Стек

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

можно не делать.) В противном случае, если j < I или j = г, возвратиться к шагу R2 (все просмотренные разряды оказались равными соответственно 1 или 0). Если же j = I, то увеличить Z на 1 и перейти к шагу R2 (встретился только один разряд, равный 0). R9. [Поместить в стек.] Поместить в стек элемент (г, Ь), а затем установить г <- j и перейти к шагу R2. R10. [Извлечение из стека.] Если стек пуст, значит, сортировка завершена. В противном случае установить I <- г + 1, извлечь из стека элемент (г, Ь), установить г i- г, b i- Ь и возвратиться к шагу R2.

Программа R {Обменная поразрядная сортировка). В следующей программе для машины MIX используются, по существу, те же соглашения, что и в программе Q. Значения регистров таковы: тИ = I - г, г12 = г, г13 = г, г14 = j, rI5 = m - b, rI6 = размер стека, если не учитывать, что в некоторых командах (отмеченных ниже) удобно оставить г13 = г - j или г14 = j - г. Двоичная природа поразрядной сортировки объясняет использование в этой программе команд SRB (поразрядный сдвиг содержимого АХ вправо), JAE (переход, если содержимое А четно) и JAO (переход, если содержимое А нечетно), определенных в разделе 4.5.2. Предполагается,

1 1 1 1 1

s s s s s

с с с

С" + Х С" + Х

С"

С"

С"

С"

в в в в

с -X с -X А-Х

R1. Начальная установка. Очистить стек. /<- 1. ri-N. 6<- 1.

Перейти к шагу R2 (опустить проверку 1 = г).

R9. Поместить в стек.

(г, Ь) стек. г11 <- Z - j. г<- j.

R2. Начать новую итерацию. i <- I, j <- г.

R3. Проверить наличие 1 в Ki.

[rl4 = Z-j]

[rI3 = i-i] [rl3-t-i]

Младший разряд г А <- разряд b ключа Ki. Перейти к шагу R4, если он равен 0. R6. Уменьшить j. j i - 1. [rl4=j-i]

Перейти к шагу R8, если j < i. [г14 = j -г] R5. Проверить наличие О в JtTj+i.

Младший разряд г А <- разряд b ключа Kj+i. Перейти к шагу R6, если он равен 1. R7. Поменять местами Ri, Rj+i.

R4. Увеличить i. i i+1. [rl3 = i-j]

Перейти к шагу R3, если г < j. [г13 = i-j] г13 <- 1.