в которой используется порядок, присутствующий в большинстве данных, чтобы породить длинные серии, значительно превосходящие емкость внутренней памяти. В разделе 5.4.1 обсуждаются также структуры данных, удобные для многопутевого слияния.

Важнейшие схемы слияния рассматриваются в разделах 5.4.2-5.4.5. Пока мы не вступим в единоборство с грубой действительностью работающих накопителей на магнитных лентах и реальных сортируемых данных, лучше, изучая характеристики этих схем, ограничиться весьма приближенным представлением о сортировке на лентах. Например, можно с легкой душой полагать (как мы делали до сих пор), что первоначальные исходные записи появляются волшебным образом в течение первой распределительной фазы. На самом деле они, вероятно, будут занимать одну из наших лент и, быть может, даже целиком заполнят несколько бобин, так как лента не бесконечна! Лучше всего пренебречь подобными техническими деталями до тех пор, пока не будет достигнуто "академическое" понимание классических схем слияния. Затем в разделе 5.4.6 мы "вернемся на землю" рассмотрев практические ограничения, которые существенно влияют на выбор схемы слияния. В разделе 5.4.6 сравниваются основные схемы слияния из разделов 5.4.2-5.4.5 с учетом множества разнообразных предположений, которые встречаются на практике.

Иные подходы к проблеме внешней сортировки, не основанные на слиянии, обсуждаются в разделах 5.4.7 и 5.4.8. Анализ разнообразных аспектов внешней сортировки заканчивается в разделе 5.4.9, в котором рассматривается важная проблема сортировки с использованием таких устройств внешней памяти, как магнитные диски и барабаны.

Когда шла работа над первым изданием этой книги, накопители на магнитной ленте использовались повсеместно, в то время как магнитные диски считались слишком уж дорогой экзотикой. Но с начала 80-х годов цена на устройства памяти с магнитными дисками разительно снизилась, и в конце 90-х годов они практически вытеснили накопители на магнитных лентах в подавляющем большинстве компьютерных систем. Таким образом, вопрос, который еще совсем недавно считался важнейшим в проблеме сортировки (а именно - разработка и анализ методов сортировки применительно к особенностям функционирования накопителей на магнитных лентах), теперь представляется не таким уж важным.

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

Из всего, что известно нам сегодня, вполне можно сделать следующий вывод: эти методы сохранят свою актуальность и в дальнейшем.

- ПАВЕЛ КЕРТИС (1997)

УПРАЖНЕНИЯ

1. [15] В тексте раздела внешняя сортировка рассматривается после внутренней. Почему нельзя вообще покончить с фазой внутренней сортировки, просто выполняя слияние записей во все более и более длинные серии с самого начала?

2. [10] Каким будет содержимое лент (аналогичное (1)-(3)), если записи Ri Кг ... Д5000000 сортируются с помощью трехленточного сбалансированного метода при Р = 2? Сравните этот случай со слиянием на четырех лентах; сколько проходов по всем данным будет сделано после первоначального распределения серий?

3. [20] Покажите, что метод сбалансированного (Р, Г-Р)-путевого слияния, примененный к 5 начальных серий, приводит к 2к проходам, если Р{Т - P)°~ < S < Р(Т - Р)*", и к 2А: + 1 проходам, если Р°(Г - Р) < S < р+Т - Pf.

Дайте простые формулы для вычисления (а) точного числа проходов как функции от 5 при Т = 2Р, (Ь) приближенного числа проходов при 5 - оо для любых Р viT.

4. [НМ15] При каком значении Р, 1 < Р < Г, значение Р{Т - Р) максимально? 5.4.1. Многопутевое слияние и выбор с замещением

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

Пусть имеется Р возрастающих серий, т. е. последовательностей записей, ключи которых расположены в порядке неубывания. Очевидным способом их слияния будет следующий: просмотреть первые записи каждой серии и выбрать из них ту, которая имеет минимальный ключ; эта запись передается на выход и исключается из входных данных, затем процесс повторяется. В любой момент времени потребуется просмотреть только Р ключей (один на каждую серию) и выбрать из них наименьший. Если наименьшими окажутся два или более ключей, выбрать можно любой из них.

Пока Р не слишком велико, этот выбор удобно осуществлять, просто выполняя Р - 1 сравнений для нахождения наименьшего из текущих ключей. Но если Р равно, скажем, 8, то можно ускорить работу, используя дерево выбора, как описано в разделе 5.2.3; затем каждый раз потребуется примерно IgP сравнений (после начального формирования дерева). Рассмотрим, например, четырехпутевое слияние с двухуровневым деревом выбора.

Шаг 1 087

Шаг 2 087 154 {

f 087 503 00 °Ml70 908 00

/ 154 426 653 00

1Мб12

Г 503 00 1 170 908 00

154 426 653 00 612 00

Шаг 3 087 154 170 <

Шаг 9 087 154 170 426 503 612 653 908 оо

Г503 00

1 170 908 00

/426 653 00 [ 612 00

00 00

f 00 00 <

I 00

в этом примере в конце каждой серии помещен добавочный ключ "оо", чтобы слияние заканчивалось естественно. Так как внешнее слияние обычно имеет дело с очень длинными сериями, эта добавочная запись с ключом "оо" не увеличит существенно длину данных или объем работы при слиянии. Кроме того, такая "концевая" запись часто служит удобным способом разделения записей файла.

В рассматриваемом процессе каждый шаг, кроме первого, заключается в замещении наименьшего элемента следующим элементом из этой же серии и в изменении соответствующего пути в дереве выбора. Так, на шаге 2 изменяются 3 узла, которые содержали 087 на шаге 1; на шаге 3 изменяются 3 узла, содержавшие 154 на шаге 2, и т. д. Процесс замещения в дереве выбора одного ключа другим называется выбором с замещением.

Мы можем по-разному рассматривать описанный процесс четырехпутевого слияния. С одной точки зрения он эквивалентен трем двухпутевым слияниям, выполняемым совместно, как сопрограммы; каждый узел дерева выбора изображает одну из последовательностей, используемых в процессах слияния. Дерево выбора, по существу, используется как приоритетная очередь с дисциплиной "наименьший из включенных первым исключается". Так же, как в разделе 5.2.3, можно было бы для реализации приоритетной очереди использовать не дерево выбора, а пирамиду. (Пирамиду, конечно, следовало бы организовать таким образом, чтобы на ее вершине появился наименьший элемент, а не наибольший, обратив для этого порядок соотношения 5.2.3-(3).) Так как пирамида не имеет фиксированного размера, можно избежать использования ключа "оо"; слияние заканчивается, когда пирамида становится пустой. С другой стороны, в приложениях, в которых используется внешняя сортировка, обычно имеют дело со сравнительно длинными записями и ключами, так что в пирамиду будут записаны вместо самих ключей указатели на них. Мы увидим ниже, что деревья выбора можно настолько удобно изображать с помощью указателей, что они (деревья), вероятно, в данной ситуации лучше пирамид.

Дерево "проигравших". На рис. 62 изображено полное бинарное дерево с 12 внешними (квадратными) узлами и 11 внутренними (круглыми); во внешних узлах записаны ключи, во внутренних - "победители" если дерево рассматривать как турнир для выбора наименьшего ключа. Меньшие числа над каждым узлом показывают традиционный способ распределения последовательных позиций памяти для полного бинарного дерева.

Чтобы определить новое состояние дерева выбора, изображенного на рис. 62, когда наименьший ключ 061 будет заменен другим ключом, нужно рассмотреть только ключи 512, 087 и 154. Если интерпретировать дерево как турнир, последние три ключа будут представлять собой проигравших в матчах с игроком 061. Это