Cтраница 3
В процессе выполнения оператора слияния с участием т входных лент каждый элемент массива независимо от т должен йыть один раз считан с ленты и один раз записан на ленту. Это значит, что сложность выполнения оператора слияния не зависит от количества входных лент т и целиком определяется длиной объединенного массива. [31]
Одной из существенных характеристик процедуры упорядочения являются требования к объемам памяти, дополнительно используемым процедурой, помимо объемов, непосредственно занятых программой упорядочения и исходным упорядочиваемым массивом. Из описания процедур упорядочения, основанных на операторе слияния ( глава 3), можно было убедиться, что в некоторых случаях дополнительные объемы памяти оказываются довольно значительными. В настоящей главе рассматриваются процедуры упорядочения, выполняемые при предельно жестких ограничениях, накладываемых на дополнительные объемы памяти. [32]
Оператор слияния Сл 1 ( Зл, т, /) должен учитывать направление упорядочения сливаемых массивов, информацию о котором он получает из шапки, и в зависимости от него выбирать для использования блок определения минимального или максимального элемента. Все сливаемые массивы, естественно, должны иметь одинаковое направление упорядочения, и на оператор слияния можно возложить функции контроля за выполнением этого условия. Оператор перемотки в случае двухсторонних магнитных лент не используется. [33]
Существование алгоритма слияния, не требующего резервных объемов памяти, очевидно для случая, когда размер меньшего из двух сливаемых массивов равен единице. Из сказанного выше по индукции следует, что алгоритм слияния, не использующий резервных объемов памяти, существует при произвольных размерах сливаемых массивов. Оператор слияния, не использующий резервных объемов памяти, представляет собой рекурсивную процедуру, описание которой непосредственно вытекает из доказательства существования алгоритма. [34]
Если сложность сравнения существенно отличается от сложности пересылки, то естественно стремиться к уменьшению числа наиболее трудоемких операций в процедуре. Оператор слияния двух упорядоченных подмассивов равного объема принадлежит к операторам, число сравнений в которых приближается к нижней теоретической границе необходимого числа сравнений. [35]
На рис. 7.7 изображен блок операторов слияния. Блоки 34 - 36 выполняют 1 - й подэтап 1-го этапа процедуры упорядочения по данным, подготовленным блоком моделирования, блоки 37 - 35 - выполняют 2 - й подэтап 1-го этапа процедуры. Количество операторов слияния, выполняемых на каждом этапе, фиксируется переменной с. Блок 50 для каждого этапа формирует список входных лент, а операторы 53 и 54 непосредственно осуществляют слияние. [36]
При использовании двухсторонних лент запись массивов на ленту как при формировании начальных участков, так и при слиянии осуществляется при движении ленты в одну сторону, а их считывание - при движении в другую сторону. Таким образом, направление упорядочения массивов в результате выполнения оператора слияния изменяется. Если направление упорядочения в окончательно упорядоченном массиве задано, то оно может быть достигнуто либо путем выбора того или иного направления упорядочения начальных участков, либо осуществлением в случае необходимости дополнительного прогона ленты. [37]
С увеличением т результативность оператора слияния монотонно возрастает, однако после / п 4ч - 5 это возрастание становится относительно медленным. Пусть массив состоит из 5 упорядоченных участков, распределенных по т входным лентам. Выполнив оператор слияния с участием т входных лент S / m раз, мы сформируем S / m упорядоченных участков, размер каждого из которых возрастает в т раз. [38]
Действительно, реализуемость слияния на том этапе, для которого выполняются указанные условия, очевидна, так как в случае чередования совпадение первых разрядов означает совпадение всех остальных. Если выполнялось четное количество операторов слияния, то к началу следующего этапа направление упорядочения участков с наибольшими номерами на лентах, которые раньше были входными, не изменяются. На ленте, которая была выходной, направление упорядочения участка с наибольшим номером будет иметь тот же знак. Если выполнялось нечетное количество операторов слияния, то направление упорядочения участков с наибольшими номерами изменится на всех лентах и все равно будет совпадать. [39]
Наиболее проста организация процедуры при использовании двойного резерва памяти. В этом случае выделяют два поля позиций равного объема ( по п позиций каждое), на одном из которых размещается исходный случайный массив. Без ограничения общности будем считать, что есть некоторое общее поле позиций М, на котором, начиная с позиции А и кончая позицией А - - п - 1, располагается исходный случайный массив, а последовательность позиций, начинающаяся с позиции В и заканчивающаяся позицией В - - п - 1, представляет резервное поле, используемое в процессе упорядочения. Общая процедура в этом случае будет использовать оператор слияния двух упорядоченных подмассивов, аналогичный описанному выше. [40]
Идея построения такой процедуры состоит в том, что начальные упорядоченные группы распределяются по входным лентам неравномерно, и поэтому входные ленты в процессе выполнения операторов слияния освобождаются неодновременно. Освободившаяся входная лента назначается выходной для следующих операторов слияния, а лента, выполнявшая до этого функции выходной ленты - входной. Размер упорядоченных участков на ленте, переназначенной из выходных во входные, естественно, будет отличаться от размеров упорядоченных участков на других входных лентах, и поэтому последовательное применение указанного алгоритма приведет к тому, что количество упорядоченных участков на всех входных лентах будет разным и размеры упорядоченных участков тоже будут отличаться друг от друга. Неравенство друг другу размеров сливаемых участков будет, естественно, снижать результативность и эффективность операторов слияния. [41]