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.


 

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

43709. ОСОБЛИВОСТІ ПРАВОВОГО СТАТУСУ ОКРЕМИХ КАТЕГОРІЙ ГРОМАДЯН ЯК СУБ’ЄКТІВ АДМІНІСТРАТИВНОГО ПРАВА 165.17 KB
  ПОНЯТТЯ ТА ЗМІСТ ПРАВОВОГО СТАТУСУ ГРОМАДЯНИНА ЯК СУБЄКТА АДМІНІСТРАТИВНОГО ПРАВА Конституція України в преамбулі закріплює прагнення Українського народу розвивати і зміцнювати демократичну соціальну правову державу. Характер їх відносин зумовлюється положенням Конституції України про те що головним обовязком держави є утвердження і забезпечення прав і свобод людини. Термін âфізична особаâ ширший за термін âгромадянинâ оскільки включає не тільки громадян України а й громадян інших держав та осіб без громадянства. Конституція...
43710. Структура дистанционного курса (ДК) «Изготовление и испытание ПТМ» 6.4 MB
  В работе представлена структура дистанционного курса (ДК) «Изготовление и испытание ПТМ»; даны рекомендации по оформлению ДК, предложена информационная, содержательная и контрольно-мониторинговая части ДК «Изготовление и испытание ПТМ».
43711. Розробка моделі цінності інформаційних ресурсів для оптимізації побудови системи захисту інформації 302.91 KB
  Мета роботи розробка моделі цінності інформаційних ресурсів для оптимізації побудови системи захисту інформації. Обєкт дослідження цінність інформації якою володіє організація що в даній роботі позиціонується як інформаційні ресурси та входить до складу активів організації. Результатом роботи є адитивна модель цінності інформації яка включає основні елементи цінності легка для сприйняття та передбачає можливість модернізації в залежності від специфіки області в якій застосовується. Продовжити вдосконалення даної моделі можна більш...
43712. Разработка программного обеспечения для сжатия изображения 4.51 MB
  Особенность изображений состоит в том, что отдельные элементы изображения находятся в определенной связи с соседними элементами. Поэтому большинство алгоритмов преобразования изображений носит групповой характер (то есть группа пикселей)
43713. Разработка мероприятия по совершенствованию системы управления персоналом на ОАО АКБ «РОСБАНК» 17.41 MB
  Управление людьми имеет практически такую же древнюю историю, как и человечество. По мере экономического развития и появления крупных организаций, управление персоналом превратилось в особую управленческую функцию, требующую специальных знаний и навыков.
43714. Повышение технического уровня подземного горношахтного оборудования 91.49 KB
  Запасы угля Вскрытие шахтного поля. Основной базой каменного угля Украины по-прежнему остаётся Донбасс. Обогащение угля не осуществляется. Основными потребителями угля являются ТЭЦ.
43715. Дослідження методів обробки пластикових матеріалів при виготовленні пакування 12.3 MB
  В результаті розробки проекту необхідно забезпечити високу продуктивність гнучкість оперативність випуску високоякісної продукції. Сучасні тенденції виробництва пластикового пакування в Україні Сучасні тенденції розвитку ринку пакувальної продукції України Використання полімерних матеріалів при виготовленні поліграфічної продукції Види полімерних матеріалів що використовуються у поліграфії Система маркування пластику Переробка пластикових відходів Етапи і методи переробки пластикових відходів
43717. Туристический кластер Псковской области 1.72 MB
  Отечественные туристские кластеры в контексте национальной стратегии отраслевого развития История развития туризма в Псковской области выступает своеобразным катализатором социально экономического развития. Задачи: Дать характеристику понятию туристский кластер; Рассмотреть классификацию туризма; Исследовать состояние и перспективы туризма в Псковской области; Охарактеризовать роль кластеров в современной экономики; Выявить возможные пути развития данной отрасли.