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

Теперь детально рассмотрим процесс создания начальных серий методом выбора с замещением. Следующий алгоритм принадлежит Джону Р. Уолтерсу (John R. Walters), Джеймсу Пэйнтеру (James Painter) и Мартину Залку (Martin Zalk), которые использовали его в программе сортировки методом слияния для компьютера Philco 2000 в 1958 году. Алгоритм включает интересный способ начального формирования дерева выбора и ргизделения записей, принадлежащих разным сериям, а также вывода последней серии по единообразной, сравнительно простой логике. (Надлежащая обработка последней серии, порожденной методом выбора с замещением, оказывается довольно сложной; блок, осуществляющий эту обработку, часто бывает камнем преткновения для программиста.) Основная идея заключается в том, чтобы рассматривать каждый ключ как пару {S,K), где К - первоначальный ключ, а 5 - номер серии, которой принадлежит данная запись. Мы получим выходную последовательность, порожденную методом выбора с замещением, если лексикографически упорядочим эти расширенные ключи (5 считается старше К).

В приведенном ниже алгоритме для представления дерева выбора используется структура данных, состоящая из р узлов. Предполагается, что j-й узел X[j] содержит с слов, начинающихся с LOC(X[j]) = Lq + cj, о < j < p. Он представляет как внутренний узел с номером j, так и внешний узел с номером р + j (см. рис. 63). В каждом узле имеется несколько полей:

KEY - ключ, находящийся в данном внешнем узле; RECORD - запись, находящаяся в данном внешнем узле (включая KEY как подполе);

LOSER - указатель на "проигравшего" в данном внутреннем случае; RN - номер серии, содержащей запись, на которую указывает LOSER; РЕ - указатель на внутренний узел, расположенный в дереве выбора выше

данного внешнего узла; PI - указатель на внутренний узел, расположенный в дереве выбора выше

данного внутреннего узла.

Например, при Р = 12 внутренний узел с номером 5 и внешний узел с номером 17 на рис. 63 будут представлены узлом Х[5] с полями KEY = 170, LOSER = Lq -Ь 9с (адрес внешнего узла с номером 21), РЕ = Lq + 8с, PI = Lq + 2с.

Значения в полях РЕ и PI являются константами; таким образом, строго говоря, нет необходимости хранить их в явном виде. Однако иногда на начальной фазе внешней сортировки для быстрой работы с устройствами ввода-вывода выгоднее хранить эту избыточную информацию, чем вычислять ее каждый раз заново.

R5. Подготовка к изменению

Т - лист

R6. Установка нового проигравшего

Рис. 66. Получение начальных серий методом выбора с замещением.

Алгоритм R (Выбор с замещением). Этот алгоритм (рис. 66) считывает записи последовательно из входного файла и записывает их последовательно в выходной файл, производя RMAX серий длиной Р или больше (за исключением последней серии). Имеется Р > 2 узлов Х[0],Х[Р - 1] с полями, описанными выше.

R1. [Начальная установка.] Установить RMAX О, RC <- О, LASTKEY оо, Q ЬОС(АГ[0]) и RQ 0. (RC - номер текущей серии, а LASTKEY - ключ последней выведенной записи. Начальное значение LASTKEY должно быть больше любого возможного ключа; см. упр. 8.) Для О < j < Р, если обозначить J = LOC(.X[j]), начальное содержимое X[j] установить следующим образом:

LOSER(J) -f-J; RN(J)-f-0; PE(J) L0C(X[[(P + y)/2j]); PKJ) L0C(X[[j72J]).

(Установка LOSER(J) и RN(J) представляет собой искусственный способ образования начального дерева путем рассмотрения фиктивной серии с номером О, которая никогда не выводится. Это - своего рода трюк; см. упр. 10.)

R2. [Конецсерии?] Если RQ = RC, то перейти к шагу R3. (В противном случае RQ = RC -Ь 1 и обработка серии с номером RC завершена. Здесь следует выполнить те специальные действия, которые соответствуют схеме слияния для последующих этапов сортировки.) Если RQ > RMAX, то выполнение алгоритма завершено; в противном случае установить RC RQ.

R3. [Вывод вершины дерева.] (Сейчас Q указывает на "чемпиона" и RQ - номер его серии.) Если RQ ф О, то вывести RECORD(Q) и установить LASTKEY KEY(Q).

R4. [Ввод новой записи.] Если входной файл исчерпан, установить RQ <- RMAX-b 1 и перейти к шагу R5. В противном случае поместить новую запись из входного файла в RECORD(Q). Если KEY(Q) < LASTKEY (т. е. эта запись не принадлежит текущей серии), то RQ RQ-b 1, и теперь, если RQ > RMAX, установить RMAX RQ.

R5. [Подготовка к изменению.] (Сейчас Q указывает на новую запись с номером серии RQ.) Установить Т (- PE(Q). (Т - переменный указатель, который будет двигаться по дереву.)

R6. [Установка нового проигравшего.] Если RN(T) < RQ или если RN(T) = RQ и KEY (LOSER (Т)) < KEY(Q), то поменять местами LOSER(T) О Q, RN(T) О RQ. (В переменных Q и RQ запоминается текущий победитель и номер его серии.)

R7. [Сдвиг вверх.] Если Т = L0C(X[1]), то вернуться к шагу R2; в противном случае Т Р1(Т) и следует вернуться к R6.

В алгоритме R говорится о вводе и вьшоде записей по одной, тогда как практически лучше считывать и записывать относительно большие блоки записей. Следовательно, на самом деле за кулисами прячутся буфера ввода и вывода; их присутствие в памяти приводит к уменьшению значения Р. Это будет пояснено в разделе 5.4.6.

"Преобразование серий с задержкой. В работе R. J. Dinsmore, САСМ 8 (1965), 48, предложено интересное усовершенствование метода выбора с замещением, использующее понятие, которое будем называть степенью свободы. Как мы видели, в каждом блоке записей, находящемся на ленте в составе серии, содержатся записи в порядке неубывания, так что первый элемент - наименьший, а последний - наибольший. В обычном процессе выбора с замещением наименьший элемент каждого блока в некоторой серии всегда не меньше наибольшего элемента в предыдущем блоке данной серии. Это соответствует "первой степени свободы" Динсмор предложил ослабить такое условие до "т степеней свободы"; новое условие не требует, чтобы наименьший элемент каждого блока был не меньше, чем наибольший элемент предыдущего блока, но он не должен быть меньше наибольших элементов каких-либо т предыдуищх блоков той же серии. Записи в отдельном блоке упорядочены, как и ранее, но соседние блоки не обязаны быть взаимно упорядоченными.

Предположим, например, что в блоках содержится только по две записи. Приведенная ниже последовательность блоков является серией с тремя степенями свободы:

I 08 50 I 06 90 I 17 27 I 42 67 51 89 (1)

Следующий блок, который может быть частью этой серии, должен начинаться с элемента, не меньшего, чем третий по порядку элемент множества {50,90, 27,67,89}, считая от наибольшего, т. е. не меньше 67. Последовательность (1) не является серией с двумя степенями свободы, так как 17 меньше, чем 50 и 90.

Серия с m степенями свободы в процессе чтения на следующей фазе сортировки может быть преобразована таким образом, что для всех практических целей она будет серией в обычном смысле. Начнем с чтения первых m блоков в m буферов и будем выполнять их т-путевое слияние; когда один из буферов исчерпается, поместим в него (т -I- 1)-й~блок, и т. д. Таким образом можно восстановить серию в виде одной упорядоченной последовательности, поскольку первое слово каждого вновь считываемого блока должно быть больше последнего слова только что исчерпанного блока или равно ему (если оно не было меньше, чем наибольшие элементы каких-либо предшествующих ему т блоков). Этот метод преобразования серии, в сущности, является т-путевым слиянием, использующим только одно устройство внешней памяти для всех входных блоков! Процедура преобразования действует, как сопрограмма, к которой обращаются каждый раз, когда нужно получить одну очередную запись серии. Можно в одно и то же время преобразовывать различные серии с различных устройств и с различными степенями свободы и сливать получающиеся серии. Это, по существу, подобно тому, как если бы процесс четырехпутевого