53474

Оптимизация процедуры Newman_sort, особенности

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-04-01

19.39 KB

1 чел.

Оптимизация процедуры Newman_sort, особенности.

Формирование результирующего упорядоченного массива осуществляется по этапам.На нулевом этапе считаем, чтот исходный массив состоит из кусков , соержащих не менее одного элемента.Сливаясь попарно ,эти куски на первом этапе формируют подмассивы ,как правило,содержание не менее чем два элементе каждый.На втором этапе каждый кусок состоит из нескольких элементов.Таким образом на i-ом этапе каждый кусок содержит не менее 2 (i) элементов.

Основная процедура , реализующая данный вариант слияния называется Newman Sort.При этом для слияния используется вспомогательный массив,равный по длине исходному массиву.В качестве основного и/или вспомогательного подмассивов поочеродно выступают то массив Б, то массив А.

Важную роль в работе процедуры Newman Sort играет и целочисленная переменная k –ый номер очередного элемента в формируемой части вспомогательного массива. После выхода из внутренней процедуры P, если вспомогательный массив упорядочился , то значение k не превосходит n. Вспомогательная логическая переменная z в результате работы процедуры принимает значение true , если в конечном итоге упорядочился массив А и false, если упорядочился массив Б.

Нетрудно также заметить, что основное пространство в процедуре занимает тело процедуры P, в котором операторы от меток К до метки Q осуществляют слияние текущей пары кусков , а последовательность операторов помеченных меткой Q подготавливает слияние следующей пары подмассивов ,если таковая найдется. Слияние во вспомогательный массив завершается, когда номер i-ого элемента из новой части основного массива окажется больше номера j элемента в правой части этого массива.

Сокращение числа вспомогательных ячеек в этой эффективной процедуре можно с помощью ряда интересных подходов для решения дополнительной памяти в процедуре Natural Merge Sort.


 

А также другие работы, которые могут Вас заинтересовать

65812. Основные методологические принципы естественной науки 26.14 KB
  Следствия принципа рациональности: Противоречие должно восприниматься как проблема аномалия слабое место теории. Разные теории принципиально по-разному объясняющие одно и то же явление не могут быть верными. Но эти теории противоречат друг другу...
65813. Признаки государства, внешние и внутренние функции государства 41 KB
  Признаки государства это его качественные свойства позволяющие отличить его от других явлений и что даже более важно т. Наличие публичной власти определяющий признак государства иногда публичную власть понимают как синоним государства отличающий его от догосударственной...
65816. Недостатки произношения свистящих звуков «С» - «Сь», «З» - «Зь», «Ц» (сигматизм, парасигматизм) 15.74 KB
  Правильная артикуляция: При произнесении свистящих звуков губы имеют тенденцию растягиваться в улыбке зубы сближены широкий кончик языка упирается в нижние резцы. Передняя часть спинки языка выгарбливается к верхним резцам при произнесении звука Ц она в первый момент образует смычку во второй щель.
65817. Государственная антимонопольная политика - ее цели и задачи 14 KB
  Для недопущения таких негативных процессов государственное антимонопольное регулирование осуществляется в двух направлениях: формирование антимонопольного законодательства; создание системы антимонопольных органов призванных осуществлять регулирование и контроль монополистической деятельности.
65818. Инвентаризация основных средств 21.5 KB
  Инвентаризация основных средств это проверка соответствия основных средств учетным записям о них. Одновременно с инвентаризацией собственных основных средств проверяются основные средства находящиеся в аренде.
65819. Интерполирование 344 KB
  Цель: Применяя методы интерполяции найти аппроксимацию функции заданной таблично. значения этой функции при указанных значениях аргумента х. Выполнить интерполирование и построить график зависимости интерполирующей функции от х на отрезке определенном крайними узлами таблицы.
65820. Исследование модели шинной ЛВС с маркерным доступом 810.5 KB
  Цель работы: Исследование особенностей построения и функционирования шинной ЛВС с маркерным методом доступа и определение основных характеристик сети. Определить основные характеристики ЛВС шинной топологии с маркерным методом доступа на основе исследования аналитической модели сети.