6.6. Формирование и распределение начальных серийа
 

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

Итак, на начальном этапе сортировки считываем некоторое количество записей исходного массива в доступную область опе¬ративной памяти и, используя подходящую сортировку массивов, получаем серию, длина которой L определяется размером доступной памяти. Полученную серию записываем в один из выходных файлов. Аналогичным образом создаем и распределяем по файлам последующие серии, пока не достигнем конца исходного файла.

Формирование начальной серии из массива записей, считанных в оперативную память, можно выполнить сортировкой с использованием пирамиды, имеющей специальную структуру. Она отличается от пирамиды, используемой для сортировки массива, тем, что ключ каждой вершины меньше ключей своих потомков (свойство №3 двоичного дерева-пирамиды высоты h). Это приводит к тому, что из пирамиды на каждом шаге выталкивается запись с наименьшим ключом. Выталкиваемая запись сразу же пересылается в выходной файл и не записывается в конец массива.

Таким образом, формирование серии происходит за три этапа: чтение из файла и заполнение массива; построение пирамиды; сортировка элементов с выталкиванием их из массива в файл. В результате массив оказывается свободным и происходит формирование следующей серии. Длины всех серий одинаковы и равны длине массива, последняя серия может иметь меньшую длину.

Этот способ может с успехом применяться и для сортировки тех файлов, все записи которой умещаются в доступную область.

Имеется более изощренный способ формирования серии посредством сортировки пирамидой, когда пирамида использует как туннель. Идея заключается в следующем. Сначала массив заполняется L записями из исходного файла и строится пирамида. На этапе сортировки после выталкивания наименьшего элемента в выходной файл из входного файла считывается очередной элемент. Если его ключ больше ключа последнего вытесненного элемента, то новый элемент включается в пирамиду и осуществляется сортировка среди L элементов. Если же ключ нового элемента меньше ключа вытесненного элемента, то последний элемент массива пересылается в начало массива (вершину пирамиды), а на его место помещается новый элемент. Длина сортируемого массива (размер пирамиды) мысленно уменьшается на единицу (L = L - 1), и в сортировке теперь участвует только (L - 1) элементов.

Такой процесс продолжается до тех пор, пока размер сортируемого массива не сократится до нуля (L = 0). Формирование очередной серии на этом заканчивается, а весь массив оказывается заполненным не отсортированными элементами. Начинается формирование новой серии: в массиве строится пирамида, ocуществляется сортировка элементов и их выталкивание в файл. Длина серии при использовании туннеля больше или равна длине массива L, при случайном распределении элементов в исходном файле средняя длина серий равна 2L.

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

Извлеченные записи пересылаются в очередной выходной файл. В таблицу считывается очередная порция записей файла для формирования следующей серии.

Начальное распределение серий по файлам в случае естественного слияния и многопутевого сбалансированного слияния не вызывает затруднений, так как все файлы имеют одинаковое число серий.

Многофазовая сортировка требует оптимального распределения по файлам. Для этого, во-первых, надо знать число серий в исходном файле, а оно становится известным только в процессе формирования серий. Во-вторых, числа серий в файлах при оптимальном распределении по (N - 1) файлам должны быть числами Фибоначчи порядка (N - 2), что возможно только при определенных значениях общего числа серий. Недостающее число серий можно дополнить пустыми сериями, причем пустые серии нужно как можно более равномерно распределить по (N- 1) файлам.