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

-71-

Число ' сопоставлений

или отображений в

расчёте на одну запись

15

Рис.6 . Зависимость от параметров упорядочения числа сопоставлений при оптимальном сопоставительном упо­ рядочении и числа отображений при упорядочении о т о - бразительным алгоритмом внутреннего упорядочения последовательности.

Тсопоставительный метод для п = 8192Г

__4е ____________________ _______________

Р и с .7 . Оценки числа отображений при оптимальном упорядочении набора из 8192 записей и числа сопо­ ставлений при оптималгаом сопоставительном упоря­ дочения того же набора

- 7 3 -

риалом для образования новых ассоциаций, а в конечном ито­ ге - правильной последовательности всех записей.

Алгоритмы, в которых подпоследовательности записей

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

программирования (например, списков типа Б и В ), будем

именовать ассоциативными. Для них характерны следующие особенности:

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

вательность записей задана не расположением записей, а

иными средствами. Иногда факт существования двух последо­ вательностей записей - правЛшной последовательности и списка типа А, представляющего исходный набор записей,-

оказывается существенным для пользователя.

б) Затраты на формирование последовательности записей

в процессе упорядочения, а, следовательно, и общие затраты

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

отличив от случая, когда их последовательность представле­ на списком типа А.

в) Ассоциативные алгоритмы позволяют более гибко испо­

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

- 7 4 -

тивных алгоритмов.

Промежуточные последовательности записей при упорядо­

чении ассоциативными алгоритмами представлены ассоциатив­

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

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

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

Изменение способа её выражения может быть выполнено с помощью операторов, рассмотренных в § 6 гл .1 .

-7 6 -

§7. Классификация алгоритмов упорядочения данных Классификация представляет собой научную систематизацию

алгоритмов и имеет как теоретическое, так и практическое зна­

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

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

Наиболее весомыми различиями логической схемы алгоритмов

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