Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

а ) Последовательность записей задана списком типа Оператор начинает работу с сопоставления к-& и /- й записей.

Если между к-й и /-й записями выполняется отношение поряд­ ка, то в силу свойства транзитивности оно выполняется и нейду всеми записями 2 сегмента и t- ii записью. £ противном случае отношение порядка не выполняется между к -й записью

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

б ) Используется список типа А или £ . Ввиду сложно реализации вставки-исключения в описках типа А и Б, явные перенумерации записей при их использовании заменяются по­ строением отдельной подпоследовательности записей, в кото­ рую в правильном порядке включаются (путём копирования)

выигравшие записи. Ври исчерпании одного из исходных с е г -

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

Число сопоставлений записей при выполнении оператора

-50-

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

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

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

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

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

~ 5 t-

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

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

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

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

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

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

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

магазинов.

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

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

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

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

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

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

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

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

- 52-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

о

- 5 3 -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 5 5 -

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

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

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

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

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

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

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

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

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

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