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.


 

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

14337. Якорное устройство судна. Экспериментальная оценка уравнения цепной линии 270.5 KB
  Тема: Якорное устройство судна. Экспериментальная оценка уравнения цепной линии. Цель работы: Ознакомление с характеристиками и физическим явлением используемом в якорном устройстве. Задача: Определить основные параметры формы тяжелой гибкой нити усилия натя...
14338. Швартовное устройство судна. Экспериментальная оценка формулы Эйлера 542.5 KB
  Лабораторная работа №1 Тема: Швартовное устройство судна. Экспериментальная оценка формулы Эйлера. Цель работы: ознакомление с характеристиками и физическим явлением используемом в швартовном устройстве. Задача: определить коэффициент трения f между канатом...
14339. Грузовое устройство судна. Экспериментальная оценка грузоподъемности и коэффициента полезного действия талей 428.5 KB
  Лабораторная работа № 2 Тема: Грузовое устройство судна. Экспериментальная оценка грузоподъемности и коэффициента полезного действия талей. Цель работы: Ознакомление с характеристиками и физическим явлением используемом в грузовом устройстве. Задача: Опре...
14340. Якорное устройство судна. Экспериментальная оценка уравнения цепной линии 341 KB
  Лабораторная работа №3 Тема: Якорное устройство судна. Экспериментальная оценка уравнения цепной линии. Цель работы: Ознакомление с характеристиками и физическим явлением используемом в якорном устройстве. Задача: Определить основные параметры формы тяжелой г...
14341. Личностный дифференциал 85.5 KB
  Личностный дифференциал Методика личностного дифференциала ЛД разработана на базе современного русского языка и отражает сформировавшиеся в нашей культуре представления о структуре личности. Методика ЛД адаптирована сотрудниками психоневрологического института и...
14342. Методика Ценностные ориентации» М.Рокича 43 KB
  Методика Ценностные ориентации М.Рокича Система ценностных ориентации определяет содержательную сторону направленности личности и составляет основу ее отношений к окружающему миру к другим людям к себе самой основу мировоззрения и ядро мотивации жизненной актив
14343. ЦЕННОСТНЫЕ ОРИЕНТАЦИИ МЕТОДИКА (М. Рокич) 41.5 KB
  ЦЕННОСТНЫЕ ОРИЕНТАЦИИ МЕТОДИКА М. Рокич Обзор Тест личности направленный на изучение ценностномотивационной сферы человека. Система ценностных ориентаций определяет содержательную сторону направленности личности и составляет основу ее отношений к окружающем
14344. Диагностика межличностных отношений (методика Т. Лири) 27.06 KB
  Диагностика межличностных отношений методика Т. Лири При исследовании межличностных отношений наиболее часто выделяются два фактора: доминированиеподчинение и дружелюбиеагрессивность. Именно эти факторы определяют общее впечатление о человеке в процессах межличн...
14345. К. ТОМАСА ОПИСАНИЯ ПОВЕДЕНИЯ ТЕСТ 69.5 KB
  К. ТОМАСА ОПИСАНИЯ ПОВЕДЕНИЯ ТЕСТ Обзор Опросник личностный разработан К. Томасом и предназначен для изучения личностной предрасположенности к конфликтному поведению выявления определенных стилей разрешения конфликтной ситуации. В России тест адаптирован Н.В. Гри...