Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 92
Текст из файла (страница 92)
[1$) Нарисуйте 4-111о-дерево, соответствующее поразрядной сортировке Мочли с обратным чтением десяти ключей. 6. [30) В некотором файле содержатся двухразрядные ключи 00, 01, ..., 99. Посте выполнения поразрядной сортировки Почли по разряду единиц мы можем повторить ту же схему по разряду десятков, поменяв ролями ленты Т2 и Т4. В каком порядке, в конце концов, расположатся ключи на Т2? т. [91] Применим лн принцип двойственности также к файлам на нескольких бобинах? «5.3.8.
Сортировка с двумя лентами Для того чтобы при выполнении слияния не происходило чрезмерного движения лент, необходимо иметь три Нб(Л. Интересно подумать о том, как можно рационально организовать внешнюю сортировку с использованием только двух лент. В 1956 году Г. Б. Демут (Н. В. Пепщге) предложил метод. представляюпшй собой комбинацию выбора с замещением и сортировки методом пузырька. Предположим, что исходные данные занимают ленту Т1, и начнем с того, что считаем в память Р+1 записей.
Теперь выведем запись с наименьпгим ключом на ленту Т2 и заменим ее следующей исходной записью. Продолжаем выводить записи, для которьш значение ключа наименьшее среди всех хранящихся в памяти в текущий иомент, сохраняя дерево выбора или приоритетную очередь из Р+ 1 элементов. Когтю ввод, наконец, исчерпается, в памяти окажется Р наибольших ключей файла; выведем их в порядке возрастания.
Теперь перемотаем обе ленты и повторим этот процесс, выполняя считывание с Т2 и запись на Т1. При каждом таком проходе на свои места помещается еще, по крайней мере, Р записей. В программу можно встроить простую проверку для определения момента, когда весь файл станет упорядоченным. Потребуется не более [()у' — 1)/Р] проходов. Задумавшись на минутку, придем к выводу, что каждый проход этой процедуры эквивалентен Р последовательным проходам сортировки методом пузырька (алгоритм 5.2.2В)! Если элемент имеет Р или более инверсий, то при вводе он окажется меньше всех элементов в дереве и поэтому будет немедленно выведен (таким образом, исчезаег Р инверсий).
Если элемент имеет менее Р инверсий, то он попадает в дерево выбора и выводится раныпе всех ббльших ключей (потеряв, таким образом, все свои инверсии). Если Р = 1, происходит то же самое, что и в методе пузырька, как следует из теоремы 5.2.21. Следовательно, общее число проходов будет равно (1/Р1, где 7 — максимальное число инверсий любого элемента. Из результатов раздела о.'2.2 вытекает, что среднее значение 7 есть Х вЂ” ~/тХ/2+ 2/3+ 0(1/~/Ю). Если размер файла не слишком превосходит объем оперативной памяти илн если файл первоначально почти упорядочен, то эта сортировка методом пузырька Р-го порядка будет выполняться довольно быстро. В действительности ей можно отдать предпочтение даже в том случае, когда имеются дополнительные накопители на магнитных лентах, поскольку весь процесс сортировки может закоичитьгя раныпе, чем оператор успеет установить третью ленту.' С другой стороны, сортировка таким методом довольно больших файлов со случайно расположенными элементами будет выполняться весьма медлеюю, так как время работы приблизительно пропорционально У~.
Рассмотрим, как реализуется этот метод для 100,000 записей в примере из раздела 5.4.6. Необходимо разумно выбрать Р, чтобы учесть междублочиые промежутки при совмещении операций чтения и записи с вычислениями. Так как в примере предполагается, что каждая запись состоит из 100 символов, а 100,000 символов заполняют оперативную память. то у нас будет место дзя двух буферов ввода и двух буферов вывода размером В, если выбрать значения Р и В, такие, что 100(Р+ 1) + 4В = 100000. Если использовать обозначения, принятые в разделе 5.4.6, то приблизительное вре- мя выполнения каждого прохода выражается как ЖС. зт(1 + р), ы = (В+ у)/В.
(2) Поскольку. число проходов обратно пропорционально Р, желательно выбрать такое В, кратное 100, которое минимизирует величину ы/Р. Элемеитаршяй анализ показывает, что минимум достигается, когда В равно приблизительно ~/249757+.~в — 7. Поэтому мы выбираем В = 3000, Р = 879. Положив в приведенных вьпне формулах Х = 100000, получаем, что число проходов (Х/Р1 будет составлять около 114, а оценка общего времени решения — примерно 8.57 ч (предполагая для удобства, что исходные данные и окончательный выходной файл также имеют В = 3000). Здесь представлен случай, когда данные занимают около 0.44 бобины; для полной бобины потребовалось бы примерно в пять раз больше времени. Можно несколько улучшить показатели, предусмотрев в алгоритме перисдическне прерывания и пересылку записей с наибольшими ключами на вспомогательную ленту, которая затем снимается, поскольку эти записи просто копируются туда и обратно после того, как они уже были расположены в требуемом порядке.
Применение быстрой сортировки. Обменная сортировка с разделением, или быстрая сортировка (алгоритм 5.2.2Я), — — это еще один метод внутренней сортировки, который предполапют почти последовательный просмотр данных. Можно ли изобрести нечто аналогичное для внешней сортировки на двух лентах'? (Х. Б. "говвЬ, САСМ 8 (1965), 649.) Это несложно сделать, воспользовавшись обратным чтением.
Предположим, что две ленты помечены 0 и 1, и представим, что файл располагается следующим образом. Лента О Лента 1 Начало ленты ("нна") вовнння (чверх') Зьхужая лознния (" верх" ) Начало ленты ("ннч") ° ЯОВТ11 <рассортировать верхний палфайл с ленты 1 и вернуть его на ленту Ц. Процедура такая же, как ЯОВТОО, но меняются местами О и 1, а также отношения е<" И ч>'.
Можно беэ труда реализовать рекурсивное обращение к этим процедурам, записывая соответствующую управляющую информацию на ленты. Если считать, что данные располагаются в случайном порядке и вероятность наличия равных ключей пренебрежимо мала, то можно оценить время выполнения этого алгоритма следующим образом. Пусть М -- число записей, помещающихся в оперативной памяти. Пусть Лм — среднее число записей, считтяваемых при обращении к БОВТОО или ЯОВТ11 применительно к подфайлу из Х записей, где Х > Лт', и пусть 1'ы — соответствующая величина для ЯОВТ01 и ЯОВТ10. Тогда имеем: если Х < М:, если К > М; Р) если Х < М; если Х > М.
К ~ ~ ~ 1 ~ ~ | я а < м т ~ ~ ! О, ЗЛ+1+ л1',)"„„„,(Ее+Уы г а), О, Я~'+ 2+ л хт"о<<а<ге% + Кя-т-" + й) Каждая лента играет роль стека. Две ленты, используемые, как представлено здесь, дают возможность считать файл линейным списком, в котором можно перемещать текущую позицию влево или вправо, копируя элементы из одного стека в другой. Следующие рекурсивные подпрограммы определяют соответствующую процедуру сортировки.
е БОВТОО [рассортировать верхний подфайл с ленты 0 и вернуть его на ленту О). Если для подфайла достаточно места в оперативной памяти, то применить к нему внутреншою сортировку и вернуть его на ленту. В противном случае выбрать одну запись В из подфайла; пусть ее ключом будет К. Читая ленту О в обратном направ- лении, копировать все записи, ключи которых > К, полу.чая таким образом новый "верхний" подфайл на ленте 1. Теперь, считывая ленту О в прямом направлении, копировать все записи с ключами, равными К, на ленту 1. Затем, вновь читая ленту О в обратном направлении, копировать все записи с ключами < К на ленту 1.
Выполнив БОВТ10 над ключами < К, скопировать ключи, равные К, на ленту О и, наконец, выполнив БОВТ10 над ключами > К, завершить сортировку. е ЯОВТ01 <рассортировать верхний псдфайл с ленты О и записать его на ленту Ц. Процедура аналогична ЯОВТОО, но последнее обращение к еЯОВТ10е заменено иа еЯОВТ11", за которым следует копирование ключей < К на ленту 1. ° БОВТ10 «рассортировать верхний подфайл с ленты 1 и записать его на ленту О). Процедура такая же, как ЯОВТ01, но меняются местами 0 и 1, а также операторы отношений е<ч и ">".
Решение этих рекуррентных соотношений (см. упр. 2) показывает, что общий объем информации, считываемой с ленты в течение фаз внешнего разделения, в среднем равен 6~1Х 1п И + О(Х) при Аг -~ оо. Мы также знаем нз формулы 5.2.2-(25), что среднее число фаз внутренней сортировки будет равно 2(Х+ 1)/(М+ 2) — 1. Если применить этот анализ к примеру со 100,000 записями, рассмотренному в разделе 5.4.6, причем полагая, что в нашем распоряжении имеются буфера по 25,000 символов и время сортировки подфайла из и < М = 1000 записей равно 2пСмт, то получится среднее время сортировки, приблизительно равное 103 мин (включея, как на диаграмме А, окончательную перемотку).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
