Таблица 2

ПРИМЕР ПОШАГОВОГО РАСПРЕДЕЛЕНИЯ

15 серий, двухпутевого слияния 9 серий и однопутевого слияния 5 серий посредством присвоения фиктивных серий. Другими словами, 15 + 9 + 5 серий, присутствующих на уровне 3, не обрабатываются в течение первой фазы слияния. Следующий алгоритм детально описывает этот процесс.

Алгоритм С (Сортировка методом каскадного слияния со специальным распределением). Данный алгоритм (рис. 75) распределяет начальные серии по лентам серия за серией, пока запас начальных серий не исчерпается. Затем он определяет, как следует выполнять слияние лент, предполагая, что имеется Г > 3 накопителей на магнитных лентах, при этом используется самое большое (Г - 1)-путевое слияние и ненужные однопутевые слияния устраняются. Лента Т может использоваться для хранения исходных данных, так как на нее не попадает ни одна начальная серия. Алгоритм работает со следующими массивами.

А [j], < j < Т: Последнее точное каскадное распределение, которое было достигнуто

АА [j], I < j <Т: Точное каскадное распределение, к которому мы стремимся

D[j], 1 < j <Т: Число фиктивных серий, которые, как мы предполагаем, присутствуют на логическом накопителе на магнитной ленте с номером j

М [j], < j < Т: Максимальное число фиктивных серий, которые желательно иметь на логическом накопителе на магнитной ленте с номером j

ТАРЕ [j], 1 < j < Г: Номер физического накопителя на магнитной ленте, соответствующий логическому накопителю на магнитной ленте с номером j

Cl. [Начальная установка.] Установить A[fc] AA[fc] D[fc] О при 2 < к < Т. Установить А[1] -f- О, АА[1] -f- 1, D[l] -f- 1. Установить TAPE[fc] -f- к при 1 <к <Т. Наконец, установить г Г - 2, j 1, 1, / О, m •(- 1 и перейти к шагу С5. (Эти действия являются одним из способов начать работу непосредственно во внутреннем цикле, уже имея соответствующую установку управляющих переменных.)

С4. Начать шаг

С1. Начальная установка

С5. Записать части исходных данных на ленту TAPE[fc]

Входные данные исчерпаны

С7. Подготовка к слиянию

С8. Каскад

С9. Опуститься на уровень

Сортировка завершена

Рис. 75. Каскадное слияние со специальным распределением.

С2. [Начать новый уровень.] (Точное распределение только что получено. Но так как еще имеются исходные данные, необходимо подготовиться к следующему уровню.) Увеличить Z на 1. Установить A[fc] *г- AA[fc] при \ <к < Т и АА [Т - fc] -f- АА [Т - fc -f-1] + А [fc] при fc = 1, 2, ..., Т-1 (именно в таком порядке). Установить (ТАРЕ [1],..., ТАРЕ [Т-1]) -f- (ТАРЕ [Т-1],..., ТАРЁ[1]) и D[fc] AA[fc-f-1] при 1 < fc < Т. Наконец, установить г •(- 1.

СЗ. [Начать подуровень г.] Установить j г. (Переменные г и j представляют "шаг (г, j)" в табл. 2, иллюстрирующей метод Фергюсона.)

С4. [Начать шаг (г, j).] Установить fc j и m А [Т - j - 1]. Если m = О и г = j, то установить г Т - 2 и вернуться к шагу СЗ; если т = О и г ф j, вернуться к шагу С2. (Переменная т представляет собой число серий, которые должны быть записаны на ленту ТАРЕ [fc]; m = О бьшает равно О только в случае, если / = 1.)

С5. [Записать части исходных данных на ленту TAPE[fc].] Записать одну серию на ленту номер ТАРЕ [fc] и уменьшить D [fc] на 1. Затем, если ввод исчерпан, перемотать все ленты и перейти к шагу С 7.

Сб. [Продвижение.] Уменьшить m на 1. Если т > О, вернуться к шагу С5. В противном случае уменьшить к на 1; если fc > О, установить т

А [Г - j - 1] - А [Т - j] и вернуться к шагу С5, если m > 0. В противном случае уменьшить j на 1; если j > О, перейти к шагу С4, в противном случае увеличить г на 1; если i < Т-1, вернуться к шагу СЗ. В противном случае перейти к шагу С2.

С7. [Подготовка к слиянию.] (К этому моменту начальное распределение завершено и таблицы АА, D и ТАРЕ описывают состояние всех лент в данный момент.) Установить M[fc] АА[/с-(-1] при 1 < < Т и установить FIRST 1. (Переменная FIRST принимает ненулевое значение только во время первого прохода слияния.)

С8. [Каскад.] Если / = О, остановиться; сортировка завершена, вывод находится на ТАРЕ [1]. В противном случае при р = Т-1, Т-2, (именно в таком порядке) выполнять р-путевое слияние с лент ТАРЕ[1], ..., ТАРЕ[р] на ТАРЕ [р + 1] следующим образом.

Если р = 1, моделировать однопутевое слияние посредством обычной перемотки ТАРЕ [2] и замены ТАРЕ[1] (+ ТАРЕ [2].

В противном случае, если FIRST = 1 и D [р - 1] = М [р - 1], моделировать р-путевое слияние, просто поменяв ТАРЕ[р] о ТАРЕ[р -I-1], перемотав ТАРЕ [р] и выполнив вычитание М [р - 1] из каждого D [1],..., D [р-1], М [1], ...,М[р-1].

В противном случае вычесть М[р-1] из всех М[1],...,М[р - 1]. Затем слить по одной серии с каждой ТАРЕ ], такой, что 1 < j < р и D [ j] < М [ j]; вычесть единицу из каждого D[j], такого, что 1 < j < р и D[j] > M[j], и помесить выводную серию на ТАРЕ[р-Ь1]. Продолжать работу, пока ТАРЕ[р] не станет пустой. Затем перемотать ТАРЕ[р] и TAPE[p-f-1].

С9. [Опуститься на уровень.] Уменьшить I на 1, установить FIRST О и установить (ТАРЕ[1],..., ТАРЕ[Т]) (ТАРЕ[Т],... ,ТАРЕ[1]). (К этому моменту все D и М - нули; таковыми они и останутся.) Вернуться к шагу С8. I

На шагах С1-С6 алгоритма С выполняется распределение, на шагах С7-С9 - слияние. Эти две части совершенно независимы одна от другой, и можно было бы хранить M[fc] и AA[fc -f-1] в одних и тех же ячейках памяти.

Анализ каскадного слияния. Каскадное слияние поддается анализу с ббльшим трудом, чем многофазное. Но этот анализ особенно интересен, поскольку содержит много замечательных формул. Настоятельно рекомендуем читателям, интересующимся дискретной математикой, самостоятельно проанализировать каскадное распределение прежде, чем читать дальше. Ведь числа имеют так много необычных свойств, открьшать которые для себя - одно удовольствие! Мы обсудим здесь лишь один из многих подходов, обращая особое внимание на методы получения результатов.

Для удобства рассмотрим случай для шести лент. При этом будем стараться получить формулы, которые обобщаются для любого Т. Соотношения (1) позволяют получить первую основную систему: