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.


 

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

15837. Семь принципов успешной автоматизации 49.5 KB
  Семь принципов успешной автоматизации Согласно мировой статистике только треть проектов разработки и внедрения информационных систем завершаются успехом. Об аналогичных исследованиях в России ничего не известно но представляется что у нас дела обстоят еще хуже. У...
15838. Дети с социально-педагогической запущенностью 44 KB
  ДОКЛАД на тему: Дети с социальнопедагогической запущенностью. Общеизвестно что кризисные состояния экономического и политического положения в стране в первую очередь отражается на наименее социально защищённом контингенте на детях. Увеличение количества детей
15839. Пути преодоления речевого недоразвития, возникшего в результате социально-педагогической запущенности, у детей младшего школьного возраста 47.5 KB
  Пути преодоления речевого недоразвития возникшего в результате социальнопедагогической запущенности у детей младшего школьного возраста Государственное бюджетное образовательное учреждение для детей нуждающихся в психологопедагогической и медикосоциальной по...
15840. Пути профилактики и коррекции социально-педагогической запущенности 29 KB
  Пути профилактики и коррекции социальнопедагогической запущенности Современная социальная ситуация сопровождается увеличением количества детей с девиантным поведением. Особое место занимает группа детей с выраженной социальнопедагогической запущенностью ко...
15841. АБСТРАКТНОЕ КИНО И СВЕТОМУЗЫКА 38 KB
  АБСТРАКТНОЕ КИНО И СВЕТОМУЗЫКА Галеев Б.М. Абстрактное кино специфическая область кинематографа; явление пограничное и экспериментальное по отношению к самому киноискусству изобразительному в своей основе связано с ним не столько по художественной специфике язы...
15842. ПЯТЬ ГОЛЛАНДСКИХ ФИЛЬМОВ, ПОСТАВЛЕННЫХ В ВООБРАЖЕНИИ 170 KB
  Питер Гринуэй ПЯТЬ ГОЛЛАНДСКИХ ФИЛЬМОВ ПОСТАВЛЕННЫХ В ВООБРАЖЕНИИ Фрагменты лекции Питера Гринуэя прочитанной на семинаре Воинствующее кино Утрехт Нидерланды 25 сентября 1988 года. Кино слишком богатое возможностями средство коммуник...
15843. ДОКУМЕНТАЛЬНОЕ КИНО - ИСКУССТВО СЛЕДУЮЩЕГО ТЫСЯЧЕЛЕТИЯ 51.5 KB
  Д. Луньков Л. Джулай ДОКУМЕНТАЛЬНОЕ КИНО ИСКУССТВО СЛЕДУЮЩЕГО ТЫСЯЧЕЛЕТИЯ Постфестивальные диалоги Дмитрий Алексеевич Луньков режиссер и сценарист теоретик и популяризатор документального кино. Мы знакомы так давно что я и запамятовала когда и где состо
15844. Условия интерференционного максимума и минимума. Оптическая разность хода 66 KB
  Для получения когерентных световых волн применяют метод разделения волны на 2 части, которые после прохождения разных оптических путей накладываются друг на друга и наблюдается интерференционная картина.
15845. Сочинение фильма 137.5 KB
  Отар Иоселиани СОЧИНЕНИЕ ФИЛЬМА1 Беседу ведет Татьяна Иенсен Искусство кино №4 1993г. Татьяна Иенсен. В одном из интервью вы обмолвились что снимая фильмы задаетесь целью не рассказать зрителю некую историю а показать. Отар Иоселиани. Ну что такое не расска...