2. [М28] В тексте раздела схематически представлена многофазная поразрядная сортировка 21 ключа. Обобщите ее для Fn ключей и объясните, какие ключи и на какой ленте оказываются в конце каждой фазы. [Указание. Рассмотрите систему счисления, использующую числа Фибоначчи; см. упр. 1.2.8-34.]

3. [МЗЗ] Распространите результаты упр. 2 на многофазную поразрядную сортировку с четырьмя или более лентами (см. упр. 5.4.2-10.)

4. [М23] Докажите, что схема распределения Эшенхерста служит наилучшим способом сортировки десяти ключей на четырех лентах без обратного чтения в том смысле, что соответствующее дерево имеет минимальную длину внепшего пути среди всех "сильных 4-fifo-деревьев" (Таким образом, это, по существу, - наилучший метод, если не учитывать время перемотки.)

5. [15] Нарисуйте 4-11£о-дерево, соответствующее поразрядной сортировке Мочли с обратным чтением десяти ключей.

► 6. [20] В некотором файле содержатся двухразрядные ключи 00, 01, 99. После выполнения поразрядной сортировки Мочли по разряду единиц мы можем повторить ту же схему по разряду десятков, поменяв ролями ленты Т2 и Т4. В каком порядке, в конце концов, расположатся ключи на Т2?

7. [21 ] Применим ли принцип двойственности также к файлам на нескольких бобинах? *5.4.8. Сортировка с двумя лентами

Для того чтобы при выполнении слияния не происходило чрезмерного движения лент, необходимо иметь три НМЛ. Интересно подумать о том, как можно рационально организовать внешнюю сортировку с использованием только двух лент. В 1956 году Г. Б. Демут (Н. В. Demure) предложил метод, представляющий собой комбинацию выбора с замещением и сортировки методом пузырька. Предположим, что исходные данные занимают ленту Т1, и начнем с того, что считаем в память Р+1 записей. Теперь выведем запись с наименьшим ключом на ленту Т2 и заменим ее следующей исходной записью. Продолжаем выводить записи, для которых значение ключа наименьшее среди всех хранящихся в памяти в текущий момент, сохраняя дерево выбораили приоритетную очередь из Р + 1 элементов. Когда ввод, наконец, исчерпается, в памяти окажется Р наибольших ключей файла; выведем их в порядке возрастания. Теперь перемотаем обе ленты и повторим этот процесс, выполняя считывание с Т2 и запись на Т1. При каждом таком проходе на свои места помещается еще, по крайней мере, Р записей. В программу можно встроить простую проверку для опреде.ления момента, когда весь файл станет упорядоченным. Потребуется не более [(Л - 1)/Р] проходов.

Задумавшись на минутку, придем к выводу, что каждый проход этой процедуры эквивалентен Р последовательным проходам сортировки методом пузырька (алгоритм 5.2.2В)! Если элемент имеет Р или более инверсий, то при вводе он окажется меньше всех элементов в дереве и поэтому будет немедленно выведен (таким образом, исчезает Р инверсий). Если элемент имеет менее Р инверсий, то он попадает в дерево выбора и выводится раньше всех больших ключей (потеряв, таким образом, все свои инверсии). Если Р = 1, происходит то же самое, что и в методе пузырька, как следует из теоремы 5.2.21.

Следовательно, общее число проходов будет равно где / - максималь-

ное число инверсий любого элемента. Из результатов раздела 5.2.2 вытекает, что среднее значение / есть N - \/ttN/2 -Ь 2/3 -Ь 0{1/VN).

Если размер файла не слишком превосходит объем оперативной памяти или если файл первоначально почти упорядочен, то эта сортировка методом пузырька Р-го порядка будет выполняться довольно быстро. В действительности ей можно отдать предпочтение даже в том случае, когда имеются дополнительные накопители на магнитных лентах, поскольку весь процесс сортировки может закончиться раньше, чем оператор успеет установить третью ленту! С другой стороны, сортировка таким методом довольно больших файлов со случайно расположенными элементами будет выполняться весьма мед.пенно, так как время работы приблизительно пропорционально N.

Рассмотрим, как реализуется этот метод для 100,000 записей в примере из раздела 5.4.6. Необходи.мо разумно выбрать Р, чтобы учесть междублочные промежутки при совмещении операций чтения и записи с вычислениями. Так как в примере предполагается, что каждая запись состоит из 100 символов, а 100,000 символов заполняют оперативную память, то у нас будет место для двух буферов ввода и двух буферов вывода размером В, если выбрать значения Р и В, такие, что

100(Р+1)+ 4Р = 100000. (1)

Если использовать обозначения, принятые в разделе 5.4.6, то приблизительное время выполнения каждого прохода выражается как

NCojt{1+p), ш{В + у)/В. (2)

Поскольку число проходов обратно пропорционально Р, желательно выбрать такое В, кратное 100, которое минимизирует величину ui/P. Элементарный анализ показывает, что минимум достигается, когда В равно приблизительно у/24975у + -/ - 7. Поэтому мы выбираем В = 3000, Р = 879. Положив в приведенных выше формулах Л = 100000, по.лучаем, что число проходов \1/Р] будет составлять около 114, а оценка общего времени решения - примерно 8.57 ч (предполагая для удобства, что исходные данные и окончательный выходной файл также имеют В = 3000). Здесь представлен случай, когда данные занимают около 0.44 бобины; для полной бобины потребовалось бы примерно в пять раз больше времени. Можно несколько улучшить показатели, предусмотрев в алгоритме периодические прерывания и пересылку записей с наибольшими ключами на вспомогательную ленту, которая затем снимается, поскольку эти записи просто копируются туда и обратно после того, как они уже были расположены в требуемом порядке.

Применение быстрой сортировки. Обменная сортировка с разделением, или быстрая сортировка (алгоритм 5.2.2Q), - это еще один метод внутренней сортировки, который предполагает почти последовательный просмотр данных. Можно ли изобрести нечто аналогичное для внешней сортировки на двух лентах? [N. В. Yoash, САСМ 8 (1965), 649.]

Это несложно сделать, воспользовавшись обратным чтением. Предположим, что две ленты помечены О и 1, и представим, что файл располагается следующим образом.

Лента О Лента 1

Начало Текущая Текущая Начало

ленты позиция позиция ленты

("низ") ("верх") ("верх") ("низ")

Каждая лента играет роль стека. Две ленты, используемые, как представлено здесь, дают возможность считать файл линейным списком, в котором можно перемещать текущую позицию влево или вправо, копируя элементы из одного стека в другой. Следующие рекурсивные подпрограммы определяют соответствующую процедуру сортировки.

• SORTOO [рассортировать верхний подфайл с ленты О и вернуть его на ленту 0]. Если для подфайла достаточно места в оперативной памяти, то применить к нему внутреннюю сортировку и вернуть его на ленту. В противном случае выбрать одну запись R из подфайла; пусть ее ключом будет К. Читая ленту О в обратном направлении, копировать все записи, ключи которых > К, получая таким образом новый "верхний" подфайл на ленте 1. Теперь, считывая ленту О в прямом направлении, копировать все записи с ключами, равными К, на ленту 1. Затем, вновь читая ленту О в обратном направлении, копировать все записи с ключами < К па, ленту 1. Выполнив S0RT10 над ключами < К, скопировать ключи, равные К, на ленту О и, наконец, выполнив S0RT10 над ключами > К, завершить сортировку.

• S0RT01 [рассортировать верхний подфайл с ленты О и записать его на ленту 1]. Процедура аналогична SORTOO, но последнее обращение к "S0RT10" заменено на "S0RT11" за которым следует копирование ключей < К на ленту 1.

• S0RT10 [рассортировать верхний подфайл с ленты 1 и записать его на ленту 0]. Процедура такая же, как S0RT01, но меняются местами О и 1, а также операторы отношений "<" и ">:

• S0RT11 [рассортировать верхний подфайл с ленты 1 и вернуть его на ленту 1]. Процедура такая же, как SORTOO, но меняются местами О и 1, а также отношения

"<" и ">:

Можно без труда реализовать рекурсивное обращение к этим процедурам, записывая соответствующую управляющую информацию на ленты.

Если считать, что данные располагаются в случайном порядке и вероятность наличия равных ключей пренебрежимо мала, то можно оценить время выполнения этого алгоритма следующим образом. Пусть М - число записей, помещающихся в оперативной памяти. Пусть Хм - среднее число записей, считываемых при обращении к SORTOO или S0RT11 применительно к подфайлу из Л записей, где N > М, и пусть Fjv - соответствующая величина для S0RT01 и SORT 10. Тогда имеем:

/ О, если N <М;

- \ 3iV + 1 + i Eo<k<NiYk + YN-i-k), если N > М;

J О, если N <М;

- \ 3iV Ч- 2 + i Eo<k<NiYk + Хм-i-k + к), если N > М.