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.


 

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

77863. Граждане (физические лица) как субъекты 29.5 KB
  Гражданин (физическое лицо) как участник правоотношений обладает рядом признаков и свойств, которые определенным образом индивидуализируют его и влияют на его правовое положение. К таким признакам и свойствам следует отнести: имя, гражданство, возраст, семейное положение, пол, состояние здоровья.
77865. Возникновение и прекращение юридических лиц 29 KB
  Он связан с необходимостью получения предварительного разрешения согласия от органов публичной власти на создание соответствующего юридического лица что обычно служит общим интересам всех участников оборота коммерческие банки и страховые компании. В соответствии с ней в регистрирующий орган представляются заявление устав и решение о создании юридического лица либо учредительный договор а также документы подтверждающие оплату регистрационного сбора и не менее 50 уставного капитала. Данные государственного реестра юридических лиц должны...
77866. Государство и МО как субъекты 27.5 KB
  Оборота как юридически равных собственников или иных законных владельцев имущества находящихся в частноправовых а не в публичноправовых отношениях друг с другом. РФ ее субъекты и муниципальные образования являются собственниками своего имущества и в этом качестве участвуют в отношениях собственности и иных вещных правоотношениях. Как собственники своего имущества ППО независимы друг от друга и выступают в гражданских правоотношениях как вполне самостоятельные равноправные и имущественно обособленные субъекты. ППО располагают...
77867. Объекты гражданских правоотношений и их основные виды 27.5 KB
  Гражданское законодательство относит деньги к движимым вещам. В гражданском обороте деньги оцениваются количеством выраженных в них единиц а не числом банкнот или монет. Вместе с тем деньги могут выступать и в роли особого товара самостоятельного предмета некоторых сделок например займа и кредита ибо последний по сути...
77868. Основания возникновения, изменения и прекращения 29.5 KB
  В действиях проявляется воля субъектов. Правомерные это действия соответствующие требованиям законов иных правовых актов и принципов права. Юридические акты правомерные действия имеющие целью возникновение изменение или прекращение. Основным видом сделки волевые действия направленные на достижение определенного правового результата.
77869. Понятие и виды сделок 28 KB
  Сделки акты осознанных целенаправленных волевых действий лиц совершая которые они стремятся к достижению определенных правовых последствий. Действительность сделки означает признание за ней качеств юридического факта порождающего тот правовой результат к которому стремились субъекты сделки. Действительность сделки определяется законодательством посредством следующей системы условий: а законность содержания; б способность лиц совершающих ее к участию в сделке; в соответствие воли и волеизъявления; г соблюдение формы...
77870. Недействительность сделок и ее последствия 30.5 KB
  Недействительность сделок и ее последствия Недействительность означает что действие совершенное в виде сделки не обладает качествами юридического факта способного породить гражданскоправовые последствия. Ничтожность сделки означает что действие не порождает и не может породить желаемые для ее участников правовые последствия в силу несоответствия закону. Оспоримость означает что действия совершенные в виде сделки признаются судом при наличии предусмотренных законом оснований недействительными по иску управомоченных лиц....
77871. Понятие, способы и пределы осуществления 30 KB
  Понятие способы и пределы осуществления Осущ. Под фактическими способами осуществления субъективного права понимается действие или система действий управомоченного лица не обладающих признаками сделок или иные юридически значимые действия. Под юридическими способами осуществления суб. Процесс осуществления суб.