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.


 

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

71746. Работа с таблицами в Microsoft Office Word 660 KB
  Таблицы в современном текстовом процессоре являются очень мощным и универсальным средством позволяющим не только наглядно и компактно разместить информацию но и придать странице любую структуру. Алгоритм создания таблицы: Для вставки в документ таблицы необходимо поставить...
71747. Освоение обработки данных с помощью СУБД 380 KB
  Студент должен уметь выполнять следующие виды работ: использовать средства СУБД Microsoft Access для формирования базы данных в режимах Таблицы и Конструктор. использовать средства СУБД Microsoft Access для создания связей между таблицами, входящими в БД.
71748. ТЕКСТОВЫЙ ПРОЦЕССОР WORD 2007 471.5 KB
  Форматирование документов осуществляется в результате следующих действий: установки параметров страницы документа; применения шрифтового оформления символов текста; задания положения абзацев на странице и установки для них отступов и интервалов слева и справа межстрочный и межабзацный интервалы...
71749. Представление информации в табличной форме 258.5 KB
  Цель работы: Научить студентов вставлять в документ таблицы, рисовать таблицы, вводить текст в ячейки таблицы, выравнивать и форматировать текст в ячейках, добавлять и удалять строки и столбцы таблицы, менять параметры ячеек таблицы, вводить формулы в ячейки таблицы.
71750. Создание и редактирование документов 914.05 KB
  Ввод текста в Word осуществляется построчно переход на следующую строку в пределах одного абзаца выполняется автоматически. Ввод текста осуществляется в ту позицию текста в которой находится курсор мерцающая вертикальная черта.
71751. Предикаты раздела WHERE оператора SELECT 55 KB
  Вводит данные в таблицу, заменяя при этом все записи, вызывающие конфликт. Этот оператор аналогичен INSERT за исключением того, что при конфликте нового значения с существующим уникальным ключом новое значение будет записано вместо старого. Первый вариант оператора просто вставит указанные...
71752. Введение в БД MySQL. Типы данных 85 KB
  Цель работы Ознакомление с базой данных MySQL: получение навыков запуска консоли для работы с MySQL корректного формирования и набора команд для работы с БД. Изучить имеющиеся типы данных для столбцов в базе данных MySQL освоить операции создания таблиц.
71753. Изменение таблицы. Выбор данных из таблиц 53 KB
  Оператор ALTER охватывает широкий набор действий, которые изменяют структуру таблицы. Этот оператор используется для добавления, изменения или удаления столбцов существующей таблицы, а также для удаления индексов. Несколько операторов ALTER могут быть объединены в одно предложение...
71754. Создание баз данных 112.5 KB
  Поскольку базы данных и таблицы MySQL хранятся как файлы файловой системы, вы столкнетесь с неприятными различиями - в поведении реализаций для Unix и Win32. Именно, все файловые системы для Win32 нечувствительны к регистру, в то время как файловые системы Unix различают регистр.