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