AOP_Tom3 (1021738), страница 91
Текст из файла (страница 91)
5.4.4 — 20.) Ндннственное различие заключается в том, что все внешние узлы рассматриваемых здесь Т1 Т2 Т3 Т4 )4 13 11 )2 13 12 — 1231 )г )1 21 (231 11 — — 213' 1131 4' 3' 3' Начальное распределение Шаг дерева 5 Шаг дерева 4 Шаг дерева 3 Шаг дерева 2 Шаг дерева 1 101 Если сравнить ее с поразрядной сортировкой, то очевидно, что оба метода имеют, в сущности, одну и ту же структуру, но обратны во времени и имеют обратное расположение содержимого на лентах: 123 (две серии длиной 1 каждая, за которыми следует одна серия длиной 3) соответствует (3, 8, в) (4) (5) (два подфайла, содержащие по 1 кл1очу, перед которыми расположен один подфайл, содержащий 3 ключа). Двигаясь в другую сторону, можно, в приннипе, построить поразрядную сортировку, двойственную многофкзному слиянию, каскадному слиянию и т.
д. Например, многофазнаму слиянию 21 серии на трех лентах, изображенному в начале раздела 5.4 2, соответствует следующая интересная поразрядная сортировка. дереньев помечены одной и той же лентой. Мы могли бы снять это ограничение, предположив, что существует окончательная фаза "сборки", на которой все записи переносятся на вынодную ленту, или могли бы добавить его к правилам для Т- б(о-деревьев, потребовав, чтобы начальный распределительный проход сортировки методом слияния был явно выражен в соответствующем дереве слияния. Иными словами, каждой схеме слияния соответствует схема распределе>гня н и ждой схеме раснределетп1я соответствует схема слияния. По некотором размышлении это становится понятным, Рассмотрим сортировку методом слияния, делающую все наоборот, т. е. разделяю1пую окончательный выводной файл на подфайлы, которые, в свою очередь, разделяются на другие подфайлы, и т.
д. Наконец, разделим файл на Я серий. Подобная схема может применяться к лентам тогда и только тогда, когда допустима соответствующая схема распределения для поразрядной сортировки Я ключей. Эта двойственность слияния и распределения почти точна; она не выполняется только в одном отношении: данные с вводной ленты должны сохраняться в разное время.
Пример с восемью ключами, рассмотренный в начале этого раздела, очевидно, является двойственным сбалансированному слиянию на четырех лентах. Пример с десятью ключами и частичными проходами соответствует следующей схеме слияния десяти серий (если скрыть фазы копирования -- шаги 6 — 11 в дереве). Т2 Т1 (0,1,...,20) ТЗ (О) (1)... (7) 2 (0,5,10,13.18) (0,5, 10, 13, 16) (1,6, 11,! 4, 19) (2,7,12, 15,20) 4 5 (8) (9) (10) (11) (12) 6 (8)(9Н10Нп)(1гН1з).,. (га) (0,2,4,5,7,9,10,12,13,15,17,18,20) (3,8,16)(4,9,17) (3,8,16)(4,9,17)(5,10,18) (6, 11, 19) ( 7, 12, 20) (1, 3,6,8, 11, 14, 16, 19) (1,3,6,8,11,14,16,19) (2,4,7,9,12,15,17,20) (0,13)(1,14)(2,15) (0,13)(1,14)(2,15) (3,16)...(7,го) Правило распределения, согласно которому ключи располагаются на лентах на каж- дом шаге, кажется магическим, но на самом деле оно имеет простую связь с системой счисления, использующей числа Фнбоначчи! (См.
упр, 2.) Обратное чтение. Двойственность поразрядной сортировки и слиянии применима также к алгоритмам, читающим ленту в обратном напранлении. Мы определили ТИо-деревья в разделе 5.4.4, и нетрудно видеть, что они подходят для поразрядной сортировки н той же мере, что и для сортировки методом слияния.
Поразрядная сортировка с обратным чтением была фактически рассмотрена Джоном Мочлн (ЛоЬп МапсЫу) еще в 1946 году в одной из первых опубликованных работ по сортировке вообще (см. раздел 5.5). Мочли на самом деле предложил следующую схему сортировки. Т4 Фаза Т1 тг (О, 1,2,...,9) (3, 6) (3, б) (1, 8) (3, бЦ1, 8) ТЗ (0, 1,8,9) (О, 1,8,9) (О) 1 (4,5) 2 (4, 5) (2, 7) 3 (4, 5Ц2, 7Ц0, 9) 4 (,5)(2,7) (2, 3, 6.
7) (9) — (9Ц8)(7)(б)(5) (0Ц1Ц2ЦЗ)(4) (0Ц1ЦЗЦЗЦ4Ц5) . (9) 8 С Эта схема не является самой эффективной среди всех возможных, но она интересна тем, что показывает: методы с частичными проходами рассматривались применительно к поразрядной сортировке еще в 1946 году, хотя в литературе по слиянию они появились лишь около 1960 года, Эффективная конструкция схем распределения с обратным чтением была предложена в работе А. Вауеэ, САСМ 11 (1968), 491-193.
Пусть дано Р + 1 лент и ;э ключей; разделите ключи на Р подфайлов, каждый из которых содержит (Я/Р) или (5/Р) ключей, и примените эту процедуру рекурсивно к каждому подфайлу. Если Я < 2Р, то один подфайл должен состоять из единственного наименыпего ключа; его и следует записать на выводную ленту. (Общая конструкция с прямым порядком Р. М. Карпа, описанная в конце раздела 5.4.4, включает этот метод как частный случай.) Обратное чтение несколько усложняет слияние, поскольку оно обращает порядок серий.
Соответствующий эффект возникает и при поразрядной сортировке. Результат оказгява< тся устойчивым илн неустойчивым в зависимости от того, какой уровень достигнут в дереве. После поразрядной сортировки с обратным чтением, когда одни внешние узлы находятся на четных уровнях, а другие .. на нечетных., для одних ключей относительный порядок различных записей с одинаковыми ключами будет совпадать с первоначальным порядком, но для других он будет пратиаапалалсеи исходному (см. упр. 6). Осцидаирйющал сортировка методом <шияння также имеет свою пару в этой двойственности. При асцпллирующей поразрнднай сортировке мы продолжаем разделять ключи, пока не достигнем подфайлов, содержащих только один ключ или достаточно малых, чтобы поддаваться внутренней сортировке. Такие подфайлы сортируются и записываются на вынодную ленту, затем процесс разделения возоб- новляется.
Например, еглв имеются три рабочие ленты и одна выводная и если ключи являются двоичными числами, мы можем сначала поместить ключи вида Ох на ленту Т1, а ключи 1х — на ленту Т2. Если иа ленте Т1 больше записей, чем может поместиться в памяти, то внонь просматриваем ее и помещаем 00х на Т2 и 01х на ТЗ.
Теперь, если подфайл ООх достаточно короткий, выполняем его внутреннюю сортировку, выводим результат, а затем начинаем обработку подфайла 01х. Подобный метод был назван Э. Х. Френдом каскадной псевдопоразрядной сортировкой [ЗАСМ 3 (1956), 157-159]; более подробно его разработали Х. Нэглер (Н. Л)аб)ег) [ЗАСМ 6 (1959), 459-468], который дал ему красочное название "метод двугланого змия", и Ч. Х. Годетт (С. Н. Сацдес)е) [ЕВМ ТесЛ. В)вс1озпге Вп!1. 12 (Арп!, 1970), 1849 — 1853]. Имеет ли поразрядная сортировка преимущество перед слиянием.
Одним важным счедствием принципа двойственности является то, что поразрядная сортировка обычна хуже сортировки методом слияния. Это связано с тем, что метод выбора с замещением по сравнению с сортировкой методом слияния имеет определенное преимущество: нет очевидного пути такого построения поразрядной сортировки, чтобы можно было использовать процедуры внутренней сортировки, требующие более одной загрузки в память за один раз. На самом деле осциллирующая поразрядная сортировка часто будет порождать подфайлы, несколько меньшие, чем объем памяти, так что ее схема распределения соответствует дереву со значительно большим числом внешних узлов, чем было бы при использовании слияния и выбора с замещением.
Соответственно возрастает длина внешнего пути дерева (т. е. время сортировки). (См. упр, 5.3.1 — ЗЗ.) Для внешней поразрядной сортировки существует, однако, одно важное применение. Предположим, например, что имеется файл, содержащий фамилии всех сотрудников большого предприятия в алфавитном порядке. Предприятие состоит из десяти отделений, и требуется рассортировать файл по отделениям, сохраняя алфавитный порядок сотрудников каждого отделения. Если файл длинный, значит, сложилась именно та ситуация, в которой следует применять стабильную поразрядную сортировку, так как число записей, принадлежащих каждому из отделений, будет, вероятно, больше числа записей, которые были бы в начальных сериях, полученных методом выбора с замещением. Вообще говоря, если диапазон ключей так мал, что набор записей с одинаковыми ключами более чем вдвое пренышает объем оперативной памяти, то разумно использовать поразрядную сортировку.
Мы видели в разделе 5.2.5, что на некоторых высокоскоростных компьютерах внутренняя поразрядная сортировка предпочтительнее слияния, поскольку "внутренний цикл" поразрядной сортировки обходится без сложных переходов. Если внешняя память очень быстрая, то дая таких машин может оказаться проблемой выполнение слияния данных с такой скоростью, чтобы поспеть за оборудованием ввода-вывода. Поэтому в подобной ситуации поразрядная сортировка, возможно, лучше слияния, особенно если известно, что ключи распределены равномерно.
УПРАЖНЕНИЯ 1. [20] В начале раздела 5.4 было определено общее сбалансированное слияние нв Т лентах с параметром Р, 1 < Р < Т. Покажите, что оио соответствует поразрядной сортировке, использующей систему счисления со смешанным основанием. 2. [М28) В тексте раздела схематически представлена многофазнаи поразрядная сортировка 21 ключа. Обобщите ее лля Р„ключей и объвсните, какие ключи и на какой ленте оказываются в конце каждой фазы. [Указание. Рассмотрите систему счисления, испааьзующую числа Фибоначчи; см. уор. 1.2.8-34.[ 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
