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.


 

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

42418. Функции. Принцип Дирихле 46 KB
  Докажите что либо одно из них делится на 5 либо сумма нескольких рядом стоящих чисел делится на 5. Докажите что какието три из них можно накрыть квадратиком со стороной 02 м. Докажите что найдутся как минимум 2 ученика отмечающих дни рождения в один месяц. Докажите что расстояние между некоторыми двумя из них меньше 05 см.
42419. Комбинаторика. Основные комбинаторные принципы и соединения 198.5 KB
  Введем некоторые важные обозначения: множества будем обозначать заглавными буквами; множества состоят из элементов которые будем обозначать малыми буквами. Такие множества будем изображать перечислением элементов заключая их в фигурные скобки. 3 Количество элементов в множестве называется мощностью и записывается как . Комбинаторные соединения Некоторая совокупность элементов данного nмножества называется выборкой.
42420. Булева алгебра. Законы логики высказываний. Эквивалентные преобразования 83 KB
  Законы логики высказываний. Теоретическая часть Всё множество формул логики высказываний с точки зрения их значения истинности разбивается на три класса: 1 тождественно истинные тавтология; 2 тождественно ложные противоречие; 3 нейтральные. Особое место в логике высказываний занимают законы логики тождественно истинные формулы тавтологии. Законы логики высказываний Закон тождества: А эквивалентно А.
42421. Равносильность формул. Закон двойственности. Логические функции 120.5 KB
  Каждая формула представляет собой функцию входящих в нее букв А В Определение1: Формулы F1 и F2 называются равносильными если при любых значениях входящих в них переменных x1x2xn эти формулы принимают одинаковые значения. Между понятиями равносильности и эквивалентности существует связь: если формулы F1 и F2 равносильны то формула F1F2 эквивалентность принимает одни и те же значения при всех значениях переменных и обратно: если формула F1F2 принимает одни и те же значения при всех значениях переменных то формулы F1 и F2...
42422. Нормальные формы формул. Проблема разрешения 89 KB
  Теорема 1 о приведении к ДНФ: Для любой формулы А можно найти такую формулу В находящуюся в ДНФ что АВ. Формула В называется ДНФ формулы А. Конечно например все ДНФ данной формулы равносильны. Выделим среди ДНФ так называемую совершенную дизъюнктивную нормальную форму формулы.
42423. Полные системы булевых функций. Многочлен Жегалкина. Теорема Поста 60 KB
  Цель работы: овладение навыками представления булевых функций в виде полинома Жегалкина. Теоретическая часть Таблицы истинности булевых функций сростом числа аргументов становятся громоздкими и неудобными. Более удобный аналитический способ задания булевых функций основан на рассмотрении двузначной алгебры Поста с операцией суперпозиции над множеством булевых функций.
42424. Минимизация булевых функций методом Квайна 686 KB
  Теоретическая часть Рассмотренные выше совершенная дизъюнктивная и конъюнктивная нормальные формы СДНФ и СКНФ используются для первоначального представления заданной переключательной функции через функции основной системы. Но эти формы не удобны для построения логических схем ЭВМ так как часто содержат элементы которые можно исключить при синтезе схем исходя из других форм представления функции. Существует ряд эффективных способов нахождения минимальной ДНФ булевой функции. Применяемая в методе Квайна операция неполного склеивания...
42425. Функциональные схемы 435 KB
  Такие схемы встречаются в электронных устройствах используемых в компьютерах калькуляторах телефонных системах и ряде других устройств. Постановка задачи синтеза логических схем По аналогии с тем как из трех элементарных частиц  протонов нейтронов и электронов порождаются различные химические элементы которые соединяясь в молекулы образуют вещества всей живой и неживой природы из трех простейших логических схем  дизъюнктора конъюнктора и инвертора можно образовать сколь угодно сложные функциональные схемы соответствующие...
42426. Нечёткие множества 218 KB
  Стандартное четкое множество строится на основе математической конструкции отсеивающей из универсального множества некоторую часть его элементов. То есть фактически любое множество определяется этим самым свойством или набором свойств S и объединяет некоторое количество не обязательно конечное счетное элементов обладающих свойством S. А теперь давайте попробуем из всей бесконечности всего в нашей Вселенной в которой очевидно есть место и для таких объектов как вода и стаканы сформировать множество на основе вполне понятного...