книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

-50-

Рассмотренный алгоритм является примером алгоритмов,

ооновывагацихся на внутренней упорядоченности частей после­ довательности, процесс которых выражается в постепенном сокращении числа внутренне упорядоченных сегментов при од­ новременном увеличения их размера вплоть до получения пра­ вильной последовательности. Будем называть такие алгоритмы алгоритмами внутреннего упорядочения многих подпоследова­ тельностей. Их процесс можно представить деревом, листьями которого являются исходные подпоследовательности, корнем -

правильная последовательность, а узлами - промежуточные внутренне упорядоченные подпоследовательности. Соединение нескольких рёбер в узле изображает процесс их объединения.

Обратимся теперь к случаю, когда между записями неко­ торого сегмента последовательности и записями, в него не входящими, отсутствуют инверсии. В этом случае 2 прямоуго­ льника, построенные на катетах треугольника внутренних от­ ношений сегмента й простирающиеся вплоть до катетов матри­ цы инверсий, должны содержать нули. Такую ситуацию будем называть внешней упорядоченностью сегмента в последователь­ ности. В этом случае получение правильной последовательно­ сти может быть осуществлено отдельным' упорядочением во внешне упорядоченном сегменте и отдельным сопоставлением и перенумерацией не входящих в него записей для полного устранения их инверсий.

Рассмотрим ещё более сложный случай, когда отсутству­

~ 5 t-

ют инверсии меаду записями, входящими в разные сегмйнты.

Назовём такую ситуацию взаимной упорядоченностью сегментов.

В этом случае пересечение 2 прямоугольников, построенных на катетах треугольников внутренних отношений оегментов,

должно содержать нули, а разделение одного сегмента на 2

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

писи исходного сегмента, причём в верхушке - очередная рассматриваемая запись, а в двух других - результатных -

записи получаемых оегментов, загружаемые через верхушки

магазинов.

Рассмотрим подробнее оператор разделения для случая,

когда последовательность задана списком типа А. Поскольку

суммарный размер результатных магазинов не больше размера

исходного, мы можем совместить их с последним, используя его концы как верхушки результатных магазинов. В процессе

разделения нас не интересует положение границы меаду ними.

Исходный магазин сделаем "двухверхушечным" , допуская воз­

можность обращения к записи на любом его конце (верхушки

совпадают с верхушками результатных магазинов). Выделим из него любую запись и назовём её опорной. Будем проверять выполнение отношения порядка между воеми остальными запи­ сями сегмента и опорной. Все записи, для k o t o j x j x не выпол­

- 52-

исходного магазина. Возможны два исхода рассмотрения:

а) Запись должна включаться в тот результатный мага­

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

верхушки к очередной записи иоходного магазина, одновре -

менно означающего "выталкивание" в исходном магазине и

"проталкивание" записи в результатном.

б ) Запись должна включатьоя в результатный магазин о

противоположного конца исходного сегмента. Выполнение

этого дейотвия откладывается, положение записи запомина­ ется и осуществляется переход к последовательному рассмот­ рению записей противоположного конца исходного сегмента,

которое выполняется по схеме, рассмотренной в пункте а ),

пока не встретится запись, которую надо включать в резуль­ татный магазин с противоположного конца исходного сегмента Эта запись и ранее оставленная запись меняются местами,

что означает одновременное помещение их в верхушки с о о т ­ ветствующих результатных магазинов.

Дальнейший процесс осуществляется по указанному сте­

реотипу, пока все записи исходного сегмента не будут рас­ смотрены. Положение верхушек результатных магазинов (они окажутся на смежных позициях в памяти) задаст при этом границу между полученными взаимно упорядоченными сегмен­ тами. Две записи, взятые из каждого из них, взаимно упоря­ дочены в силу транзитивности отношения порядка, так как

о

- 5 3 -

го взаимно упорядоченного с двумя полученными сегмента,

располагая её между ними. Число сопоставлений записей при разделении сегмента определяется числом его записей.

Алгоритм упорядочения, основывающийся на использова­ нии взаимной упорядоченности, начинает работу с разделен® исходной последовательности. Затем каждый из полученных взаимно упорядоченных сегментов (кроме того , что содержит единственную опорную запись, если таковой рассматривается)

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

корнем, которого является исходная последовательность, а

листьями - примитивные взаимно упорядоченные сегменты.

Прочив узлц дерева представляют промежуточные взаимно упо­ рядоченные сегменты, а рёбра, исходящие из одного узла,

показывают процесс разделения сегментов.

Сопоставительные алгоритмы внутреннего и взаимного упорядочения многих подпоследовательностей отличаются от простейших сопоставительных алгоритмов тем, что записи рассматриваются как элементы трехъярусной иерархической структуры,данных: вся последовательность записей - её вер­ хний уровень* подпоследовательности - оредний, заш ей -

низший уровень., Иначе говоря, в процессе упорядочения за­

писи рассматриваются не изолированно друг от друга, а в оп­ ределённых ассоциациях. Изменение положения записей в по -

следовательности, кроме конечной цели - получения правиль­

ной последовательности, служит также средством трансформа­ ции этой динамической структуры данных. Такой процесс поз­ воляет как бы обобществить часть действий, которые произ­ водились по отдельности с каждой записью в простейших ал­ горитмах (но и в простейших алгоритмах небольшие усложне­ ния промежуточных структур данных позволяют добиться не­ которого выигрыша в производительности).

Рассмотрим ещё одну группу алгоритмов упорядочения,

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

довательности все предшествующие записи образуют подмноже­

для которых оно выполняется. В силу этого обстоятельства дихотомическое дерево, в котором любой узел, корень и лис­ тья представляют записи, приобретает особое значение сре­ ди прочих деревьев при рассмотрении их с позиций удобства задания упорядоченности записей: записи правильной последо­ вательности можно разместить в дихотомическом дереве таким образом, что в левой ветви каждого узла (или корня дерева)

будут содержаться записи обязательно меньшие той, которая представлена этим узлом, а в правой - не меньшие (равные ей записи, в принципе, могут быть расположены в любой вет­ ви ). При включении в дерево новой записи она сначала долж­ на быть соотнесена с корневой записью дерева. В одну из ветвей, идущих от корня, новая запись определённо не может

- 5 5 -

попасть, другая же ветвь представляет подмножество неопре-

делённости (поиска). С корневой записью этой ветви должно выполняться следующее сопоставление новой записи, аналоги­ чным образом приводящее к сокращению подмножества поиска.

В процессе такого поиска места в дереве новая запись нал

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

пись становится листом, представляющим указанную ветвь в

дальнейшем. Акт её включения в дерево состоит в образова­ нии соответствующего нового адреса связи.

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

идеальном случае равенства мощностей правой и левой ветви для каждой вершины дерева число сопоставлений включаемой

записи равно EogJn+iL Если выбор корня и очередность вклю­ чения записей никак не связывается со значением их управ­

Как показано в [ з ] , при построении дерева записей пу­ тём относительно небольших издержек на так называемые ло­ кальные перестройки дерева можно поддерживать приемлемую его форму, что позволяет существенно сократить число сопо­ ставлений записей при построении дерева и в дальнейшем -

- 5 6 -

при поиска в дереве. Деревья такого рода именуются подрав-

ненннми.

Алгоритмы упорядочения путём построения дихотомичес­ кого дерева записей на основе их сопоставления будем имено­ вать сопоставительными алгоритмами включения в дихотомиче­ ское дерево.

§ 4. Метод упорядочения, базирующийся на отображении множества записей на вектор памяти

Вектор памяти является естественным упорядоченным мно­ жеством .объектов в ЭВМ, пригодным для осуществления упоря­ дочения записей путём отображения их множества на упорядо­ ченное множество объектов ( " отобразительное" упорядочение).

Идея такого упорядочения в случае отсутствия ограни­ чений на размер вектора - проста. С помощью некоторой фун­ кции соответствия устанавливается соответствие элементов вектора и записей по значению их управляющих слов. В даль­ нейшем используемый вектор будем именовать вектором значе­ ний. Один элемент вектора соответствует обычно ассоциации записей с определённым значением управляющего слова, т .е .

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

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

- 5 7 -

I . Функция соответствия. В простейшем случае ~,,1упорядо-

чения по возрастанию или убыванию значений единственного управляющего поля - соответствие записей и элементов век­ тора подразумеваемое: значение поля используется как номер элемента вектора. При упорядочении по оложному управляюще­ му слову значения всех входящих в него полей должны быть сведены к единому коду, называемому приведённым управляю­ щим словом и используемому далее как номер элемента векто­ ра . Так, если отношением порядка для одного поля является

■>, , а для другого ^ , значение одного из них должно заме­ няться (например, вычитанием из наибольшего возможного значения этого поля) с целью сведения к единому отношению порядка. Значение поля, представленное числом с плавающей запятой, должно быть однозначно и в соответствии с его ве­ личиной отображено на последовательность целых чисел, ка­ ковыми являются номера элементов вектора. Для этого поле рассматривается как составное, старшей частью которого яв­ ляется порядок (кодировка его знака должна быть следующей:

плюс - " I " , минус - "О "), а младшей мантисса. Значения отрицательных порядков должны заменяться на значения, по­ лученные вычитанием модуля исходных из наибольшего модуля порядка.д0 ошс ПОр П0 лагал0 сь , что правильная последова­ тельность управляющих полей представлена монотонно возра­ стающей или убывающей последовательностью значений. Испо­ льзование нетривиальной функции соответствия при упорядо­ чении отображением позволяет сделать исключение из этого правила, расширяя возможности упорядочения.

Здесь возможны два варианта:

а)Таблично задана функция соответствия: она имеет

вид оглавления элементов вектора. Согласно значениям управ­ ляющих полей осуществляется прямой доступ к элементам огла­ вления, полные адреса которых линейно зависят от этих зна­ чений. Злемент оглавления, содержащий адрес элемента век­

тора, служит посредником между последним и значением поля

при его отображении на вектор. Пооледукхций за отображением записей просмотр элементов вектора производится в порядке монотонного изменения адресов элементов.

б) Полные адреса элементов вектора линейно зависят от

значений управляющих полей,но просмотр элементов вектора,

осуществляемый после -отображения всех записей, выполняется

в порядке,заданном списком типа Б - оглавлением вектора.

Например, в случае упорядочения слов, заданных в коде

"М2", по первым их буквам, слова, начинающиеся с буквы А,

элемент и, следовательно, попадут в начало правильной по­ следовательности. При использовании варианта б) слова, на­ чинающиеся с А, отображаются на 70-й по номеру элемент ве­ ктора, но поскольку 1 -й элемент оглавления, используемого при просмотре элементов вектора, содержит указание именно этого элемента вектора, все слова, начинающиеся с А, ока­ зываются опять-таки первыми в правильной последовательно­

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

П. Тип результирующего списка. Если результат упоря­ дочения должен быть представлен списком типа В и в исход­ ном списке допустимо существование записей с одинаковым значением управляющего слова ( записей—"синонимов" ) . отоб­ ражением каждой ассоциации таких записей является односш -

зный список, фиксаторы начала и конца которого являются содержанием элемента вектора, соответствующего ассоциации,

Первоначально списки пусты, т .е , содержимым каждого фикса­ тора конца является адрес фиксатора начала списка. В про­ цессе отображения записей на вектор они включаются в соот­ ветствующие списки, содержимое фиксатора конца которых со ­ ответственно изменяется. Такое задание ассоциаций записей предельно упрощает процесс последующего распределения мест в правильной последовательности: конец описка, соответст­ вующего начальной ассоциации записей, связывается с нача­ лом списка, соответствующего 2 -й по порядку ассоциации,

его конец - с началом следующего списка и т .д . В этом про-

цессе используется содержимое фиксаторов (происходит по­ следовательный просмотр вектора фиксаторов).

Если результат упорядочения должен быть задан списком тина А или Б, отображением ассоциаций записей являются счётчики числа записей в каждой ассоциации. Первоначально счётчики пусты. При отображении каждой записи на вектор к содержимому соответствующего счётчика прибавляется I . Про­ цесс распределения мест в правильной последовательности,

выполняемый после отображения всех записей, более сложен,