(Слияние всегда завершается в тот момент, когда происходит обмен л-го элемента вспомогательной области. В результате применения этого метода записи вспомогательной области обычно переставляются.)

Тот же трюк применяется при слиянии сначала зон Zi vi z2, затем - z2 vi z3, ..., Zm-i и Zmt для этого необходимо выполнить 0(тп) = 0{N) операций. Поскольку ни один элемент не имел более п инверсий, часть массива Zi ... Zm оказывается, таким образом, полностью рассортированной.

Для окончательной "доводки" рассортируем записи Rn+\-2s Rn методом вставок за 0{s) = 0{N) шагов. В результате s наибольших элементов окажутся в области А. Затем применим все тот же трюк с областью А и сольем Ri ... Rn-2s с Rn+i-2s Rn-s (но поменяем везде ролями "левое" и "правое", а также отношения "меньше" и "больше"). В конце рассортируем записи Rn+i-s Rn методом вставок.

Последующее усовершенствование рассматривается в работе J. Katajainen, Т. Pasanen, J. Teuhola, Nordic J. Computing 3 (1996), 27-40. Проблема устойчивости слияния на месте рассматривается в ответе к упр. 5.5-3.

19. Вагоны можно перенумеровать таким образом, чтобы в конечной перестановке их номера были упорядочены: 12 ... 2"; так что это, по существу, задача сортировки. Прогоним сначала первые 2" вагонов через п - 1 тупиков, расположив их в порядке убывания номеров и поместив их в п-й тупик так, чтобы наименьший элемент оказался на входе в тупик (на вершине стека). Затем прогоним остальные 2"" вагонов через п - 1 тупиков, расположив их в порядке возрастания непосредственно перед п-и тупиком. И наконец, сольем эти две последовательности очевидным способом.

20. Дополнительную информацию можно найти в работе R. Е. Tarjan, JACM 19 (1972), 341-346.

22. См. Information Processing Letters 2 (1973), 127-128.

23. Слияние можно представить в виде бинарного дерева, все внешние узлы которого находятся на уровнях [lgAJ и [IgAl. Таким образом, максимальное число сравнений равно длине минимального внешнего пути на бинарном дереве с ЛГ внешними узлами (формула 5.3.1-(34)) минус ЛГ - 1, поскольку при f{m, п) = т-i-п - 1 получим максимум и имеется ЛГ - 1 слияний (см. также соотношение 5.4.9-(1)).

Обобщенная методика анализа асимптотических свойств такого рекуррентного соотношения при помощи преобразования Меллина представлена в работе Р. Flajolet, М. Golin, Acta Informa.tica 31 (1994), 673-696. В частности, в ней показано, что среднее количество сравнений равно NlgN - ON + 5{lgN)N + 0(1), а дисперсия х .345ЛГ. Здесь 5 есть непрерывная функция с периодом 1 и средним значением О, а

In 2 2 1п2(т-Ы)(т--2) 2т = 1.24815 20420 99653 84890 29565 64329 53240 16127-I-.

Суммарное число сравнений при ЛГ -> оо хорошо аппроксимируется методом нормального распределения; дополнительный анализ выполнен в работе Н.-К. Hwang, М. Cramer, Random Structures и Algorithms 8 (1996), 319-336; 11 (1997), 81-96.

РАЗДЕЛ 5.2.5

1. Нет, потому что после первого просмотра поразрядная сортировка вообще не будет выполняться, если распределяющая сортировка неустойчива. (Но предложенный способ распределяющей сортировки можно было бы применить к поразрядной СЦ-сортировке, на что указано в последнем абзаце этого раздела.)

2. Это алгоритм "антиустойчивой" сортировки, прямо противоположной устойчивой. Элементы с одинаковыми ключами располагаются в обратном порядке, поскольку при первом просмотре записи сканируются от Rn до Ri. (Это действительно удобно, так как в строках 28 и 20 программы R Л приравнивается к О, но, разумеется, вовсе необязательно выполнять первый просмотр в обратном направлении.)

3. Если стопка О не пуста, то ВОТМ[0] уже указывает на первую запись; если же она пуста, то мы устанавливаем Р <- LOC (ВОТМ [0]), а впоследствии устанавливаем в LINK (Р) указатель на первую непустую стопку.

4. Если осталось выполнить четное число просмотров, то поместить стопку О в начало стека (в очередности от первых элементов к последним), затем стопку 1, стопку (М - 1); в результате записи будут упорядочены относительно уже проанализированных разрядов ключей. Если осталось выполнить нечетное число просмотров, то поместите в начало стека стопку (М - 1), затем - стопку (М - 2), ..., стопку 0; в результате записи расположатся в обратном порядке относительно уже рассмотренных разрядов ключей. (Это правило, по-видимому, впервые опубликовал Э. X. Френд (Ё. Н. Friend) [JACM 3 (1956), 156, 165-166].)

5. Замените строку 04 строкой ENT3 7, а таблицы R3SW и R5SW следующими таблицами,

R3SW LD2 KEY,1(1:1)

LD2 KEY,1(2:2)

LD2 KEY,1(3:3)

LD2 KEY,1(4:4)

LD2 KEY,1(5:5)

LD2 INPUT,1(1:1)

LD2 INPUT,1(2:2)

LD2 INPUT.1(3:3)

R5SW LDl INPUT,1(LINK)

: (Повторить предыдущую строку еще шесть раз.) DEC1 1 I

Время выполнения новой программы вычисляется путем замены "3" на "8"; оно равняется (11р - l)iV + WpM + 12р-4Е + 2 при р = 8.

6. (а). Проанализируйте размещение (iV-)-1)-го элемента. Рекуррентное соотношение

к + 1 М-к

PM(N+\)k - PMN(k + \) Н--JPMNk

эквивалентно указанной в условии формуле. (Ь) п-я производная удовлетворяет соотношению S(N+i)() = (1 - п/М)9м1г{) + {{1 - z)/M)g-mn\z), что доказывается индукцией по п. Полагая, что z - 1, находим дм1г{1) = {1 - п/М)М-, поскольку дмо{г) - z. Следовательно, теап(амл) = (1 - 1/М)М, var(aMiv) = (1 - 2/М)М{М - 1) -Ь (1 -1/М)М- (1 - 1/М)2м2. (Обратите внимание на то, что производящая функция для Е в программе R есть guNizY.)

7. Пусть R - поразрядная сортировка, RX - обменная поразрядная сортировка. Укажем некоторые важные сходные черты и отличия. RX продвигается от старших цифр к младшим, R - наоборот. В обоих методах просматриваются цифры ключей, а сами ключи не сравниваются, В RX всегда М = 2 (см., однако, упр. 1). Время выполнения для R почти не меняется, а для RX оно очень чувствительно к распределению цифр. В обоих случаях время выполнения пропорционально 0{N log К), где К - диапазон изменения ключей, но константа пропорциональности для RX больше. С другой стороны, если цифры старших разрядов ключей распределены равномерно, то среднее время выполнения для RX будет

равно 0{N log Л) независимо от величины К. Сортировка R требует наличия полей связи, а RX работает с "минимальной памятью" Внутренний цикл в R больше подходит для компьютеров с конвейерной архитектурой.

8. При последнем просмотре стопки следует сцепить в другом порядке; например, если М = 256, то стопка (10000000)2 должна быть первой, за ней - стопка (10000001)2, стопка (11111111)2, стопка (00000000)2, стопка (00000001)2, стопка (01111111)2. Это изменение порядка сцепления легко осуществить путем модификации алгоритма Н или изменения стратегии распределения памяти при последнем просмотре (см. табл. 1).

9. Можно сначала отделить отрицательные ключи от положительных, как в упр. 5.2.2-33, или же при первом просмотре преобразовать ключи и записать их в дополнительном коде. Можно также после последнего просмотра отделить положительные ключи от отрицательных, изменив порядок расположения последних, но метод из упр. 5.2.2-33 для этого уже не годится.

11. Без первого просмотра ключи при помощи нашего метода все равно будут полностью рассортированы, потому что (по чистой случайности) ключ 503 уже предшествует ключу 509. Без первых двух просмотров было бы 1-I-1-I-0-I-0-I-0-I-1-I-1-I-1-I-0-I-0 = 5 инверсий.

12. После обмена R/t с Л[Р] на шаге М4 (упр. 5.2-12) можно сравнить Kk с Kk-i- Если Кк меньше, то сравниваем его с Кк-2, Кк-з, пока не встретим Кк > Kj. Тогда устанавливаем (Rj+i,... ,Rk-i,Rk) <- (Rk,Rj+i,... ,Rk-i), не меняя полей LINK. Удобно принудительно поместить с левого конца массива искусственный ключ Ко, который < всех других ключей.

14. Если исходная перестановка карт требует к чтений в смысле упр. 5.1.3-20 и если при каждом просмотре карты раскладываются в т стопок, то придется выполнить не менее flogm 1 просмотров. (Рассмотрите обратный переход - от упорядоченной колоды к исходной; при каждом просмотре число чтений увеличивается не более чем в т раз.) Данная перестановка требует четырех чтений для возрастающего порядка и десяти чтений для убывающего порядка. Поэтому сортировка в порядке убывания требует четырех просмотров при двух стопках и трех просмотров при трех стопках.

И обратно, этого оптимального числа просмотров достаточно для сортировки. Присвойте картам номера от О до А; - 1 в соответствии с тем, на каком по порядку сеансе была прочитана карта, и примените поразрядную МЦ-сортировку в системе счисления с основанием т. JCm. Martin Gardners Sixth Book of Matliematical Gaines (San Francisco: W. H. Freeman, 1971), 111-112.]

15. Пусть требуется к чтений и можно раскладывать карты в т стопок. Порядок обращается при каждом просмотре: если необходимо к чтений в одном направлении, то в обратном направлении понадобится п + 1 - к чтений. Минимальное число просмотров есть либо наименьшее четное число, большее или равное log„, к, либо наименьшее нечетное число, большее или равное log„,(n + 1 ~ к). (Если отталкиваться от рассортированной перестановки, то нетрудно заметить, что после первого просмотра перестановка требует не более чем т чтений для убывающего порядка, после второго - не более чем чтений для возрастающего порядка и т. д.) Нашу перестановку можно рассортировать в порядке возрастания за min(2, 5) = 2 просмотра, а в порядке убывания - за min(3,4) = 3 просмотра, если раскладывать карты только в две стопки.

16. Обеспечим, чтобы каждая строка завершалась специальным символом null, который меньше кода любой буквы в алфавите. Выполните поразрядную сортировку слева направо, причем перед этим нужно связать все строки в единый блок данных. Затем обработайте каждый блок {к = 1, 2, ...), в котором содержится более одной отличной