Cтраница 2
Определим количество сравнений, требуемых для выполнения каждого из операторов слияния. [16]
Рассмотрим один из возможных операторов такого типа, являющийся некоторым обобщением оператора слияния. Отметим прежде всего тот факт, что для нахождения объекта ( элемента) из заданной группы в g объектов с минимальным ( или максимальным) значением признака требуется по крайней мере g - 1 сравнение признаков. Объекты предполагаются при этом неупорядоченными. Примеры построения алгоритмов сравнения для поиска минимального элемента из неупорядоченной группы элементов приведены на рис. 3.6. Используя алгоритм сравнения такого типа, можно организовать слияние нескольких упорядоченных подмасси-вов в один массив. [17]
Из формулы (7.8) особенно ясно, что увеличение количества входных лент резко увеличивает результативность и эффективность группы операторов слияния. [18]
Как только блок 11 обнаружит исчерпание неупорядоченного массива на 1 - й ленте, последовательно осуществляется по одному оператору слияния 1-го, 2-го и 3-го рангов, после чего упорядочение заканчивается. [19]
Естественно было бы попытаться наложить на оператор слияния двух упорядоченных подмассивов дополнительное ограничение: объемы памяти, используемые оператором слияния дополнительно к объемам, занимаемым исходными объединяемыми подмассивами, должны быть минимальными. [20]
Составление блок-схемы программы, для Случая, когда количество начальных групп превышает ( М - 2) 3 и требуется использовать операторы слияния более высокого ранга, не представляет трудностей. [21]
Идея построения такой процедуры состоит в том, что начальные упорядоченные группы распределяются по входным лентам неравномерно, и поэтому входные ленты в процессе выполнения операторов слияния освобождаются неодновременно. Освободившаяся входная лента назначается выходной для следующих операторов слияния, а лента, выполнявшая до этого функции выходной ленты - входной. Размер упорядоченных участков на ленте, переназначенной из выходных во входные, естественно, будет отличаться от размеров упорядоченных участков на других входных лентах, и поэтому последовательное применение указанного алгоритма приведет к тому, что количество упорядоченных участков на всех входных лентах будет разным и размеры упорядоченных участков тоже будут отличаться друг от друга. Неравенство друг другу размеров сливаемых участков будет, естественно, снижать результативность и эффективность операторов слияния. [22]
Это значит, что если среди сливаемых участков есть хотя бы одна пара участков неравной длины, то можно, не изменяя сложности, увеличить результативность оператора слияния, распределив суммарный размер этой пары поровну между обоими участками. [23]
Возникает вопрос, нельзя ли так построить алгоритмы упорядочения, чтобы, с одной стороны, начинать его с распределения всей исходной информации по начальным упорядоченным участкам и подключения всех лент к выполнению операторов слияния и, с другой стороны, использовать в качестве входных все ленты, за исключением одной, выполняющей в данном операторе слияния функции выходной ленты. [24]
Если описываемый метод внешнего упорядочения выполняется с использованием односторонних магнитных лент, то после формирования ( М - 2) - х участков любого ранга требуется перемотка всех лент к началу участков для выполнения операторов слияния. После выполнения оператора слияния может потребоваться еще одна перемотка ( хотя и не обязательно) для записи новых участков с начала ленты. [25]
Недостатком метода внешнего упорядочения, описанного в § 7.4, является то, что ленты, хранящие исходный неупорядоченный массив, не освобождаются практически до самого конца выполнения процедуры и поэтому не могут участвовать в выполнении операторов слияния. Этот недостаток может оказаться особенно существенным в случае, когда количество лент мало или когда исходная информация занимает несколько лент. [26]
Если описываемый метод внешнего упорядочения выполняется с использованием односторонних магнитных лент, то после формирования ( М - 2) - х участков любого ранга требуется перемотка всех лент к началу участков для выполнения операторов слияния. После выполнения оператора слияния может потребоваться еще одна перемотка ( хотя и не обязательно) для записи новых участков с начала ленты. [27]
Если используются двухсторонние магнитные ленты, то при переназначении выходной ленты во входную изменяется направление ее движения и, следовательно, направление упорядочения сливаемой информации. Для того чтобы операторы слияния могли выполняться, нужно, чтобы изменилось направление упорядочения в сливаемых участках и на других лентах. Это значит, что - участки м-аесива - - упорядоченные. Направлении возрастания и в направлении убывания, должны быть заранее и определенным образом размещены на всех лентах. [28]
Изменяется только алгоритм операторов слияния двух упорядоченных подмассивов таким образом, чтобы это слияние могло быть выполнено без использования резервных объемов памяти. [29]
Действительно, реализуемость слияния на том этапе, для которого выполняются указанные условия, очевидна, так как в случае чередования совпадение первых разрядов означает совпадение всех остальных. Если выполнялось четное количество операторов слияния, то к началу следующего этапа направление упорядочения участков с наибольшими номерами на лентах, которые раньше были входными, не изменяются. На ленте, которая была выходной, направление упорядочения участка с наибольшим номером будет иметь тот же знак. Если выполнялось нечетное количество операторов слияния, то направление упорядочения участков с наибольшими номерами изменится на всех лентах и все равно будет совпадать. [30]