ОСНОВНЫЕ ИДЕИ И ХАРАКТЕРИСТИКИ ПРИМЕНЯЕМЫХ, МЕТОД СОРТИРОВКИ - Структуры и алгоритмы обработки данных
МЕТОДОВ
МЕТОД СОРТИРОВКИ
Пирамидальная сортировка
Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность aI, aI+1,...,aK называется (i, k)-пирамидой, если неравенство
AJ?min(a2j, а2j+1) (*)
Выполняется для каждого j, j=i,...,k для которого хотя бы один из элементов a2j, a2j+1 существует.
Например, массив А является пирамидой, а массив В не является.
А=(а2 , а3 , а4 , а5 , а6 А7 , а8 )=(3, 2, 6, 4, 5, 7)
В=(b1, b2, b3, b4, b5, b6, b7)=(3, 2, 6, 4, 5, 7)
Свойства пирамиды
- 1. Если последовательность aI, aI+1,...,аK-1, aK является (I, k)-пирамидой, то последовательность aI+1,...,aK-1, полученная усечением элементов с обоих концов последовательности, является (I+1, k-1)пирамидой. 2. Если последовательность a1...aN - (1, n)-пирамида, то а1 - минимальный элемент последовательности. 3. Если a1, a2...,aN/2,aN/2+1,...aN-произвольная последовательность, то последовательность aN/2+1,...,aN является (N/2+1, n)-пирамидой.
Процесс построения пирамиды выглядит следующим образом. Дана последовательность aS+1,...,aK, которая является (S+1, k)-пирамидой. Добавим новый элемент х и поставим его на S-тую позицию в последовательности, т. е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность - (S, k)-пирамида. Иначе найдутся элементы a2s+1,a2s такие, что либо a2s < aS либо a2s+1 < aS.
Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы aS и a2s. В результате получим новую последовательность aS',aS+1,..., a2s',..., aK. Повторяем все действия для элемента a2s' и т. д. пока не получим (S, k)-пирамиду.
Пирамидальная сортировка производится в два этапа. Сначала строится пирамида из элементов массива. По свойству (3) правая часть массива является (N/2+1, n)-пирамидой. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в нее не войдут все элементы массива. Тогда по свойству (2) первый элемент последовательности - минимальный.
Произведем двустороннее усечение: уберем элементы a1,aN. По свойству (1) оставшаяся последовательность является (2, n-1)-пирамидой. Элемент a1 поставим на последнее место, а элемент aN добавим к пирамиде a2,...,aN-1 слева. Получим новую (1, N-1)-пирамиду. В ней первый элемент является минимальным. Поставим первый элемент пирамиды на позицию N-1, а элемент aN-1 добавим к пирамиде a2,...,aN-1, и т. д. В результате получим обратно отсортированный массив.
Величины М и С в процессе построения (L, R)-пирамиды имеют следующие оценки MПир?log (R/L)+2, CПир?2 log (R/L)
Общее количество операций сравнений и пересылок для пирамидальной сортировки: C ? 2N log N+N+2, M ? N log N+6.5N-4. Таким образом, С=O(N log N), М=O(N log N) при N > ?.
Отметим некоторые свойства пирамидальной сортировки. Метод пирамидальной сортировки неустойчив и не зависит от исходной отсортированности массива
Похожие статьи
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
ОПИСАНИЕ ПРОГРАММЫ, ОСНОВНЫЕ ПЕРЕМЕННЫЕ И СТРУКТУРЫ - Структуры и алгоритмы обработки данных
ОСНОВНЫЕ ПЕРЕМЕННЫЕ И СТРУКТУРЫ Struct BD { char FIO[32]; // фоpмат <Фамилия>_<Имя>_<Отчество> int numberO; char dolzhnost[32]; char dateB[8]; }...
-
ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ - Структуры и алгоритмы обработки данных
В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной...
-
Определение методов реинжиниринга информационных систем Основные задачи, которые стоят перед проектировщиком, занимающимся реинжинирингом информационных...
-
МЕТОД КОДИРОВАНИЯ - Структуры и алгоритмы обработки данных
Код Шеннона Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов. Тогда по теореме Шеннона из п. 5.1 . Код Шеннона,...
-
ПОСТАНОВКА ЗАДАЧИ - Структуры и алгоритмы обработки данных
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные По дням рождения и ФИО ,...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
Построение ER диаграмм - Модернизация структуры базы данных на основе анализа требований предприятия
При построении моделей информационных систем важнейшей методикой является ER-моделирование или построение диаграмм сущность-связь. Сущность представляет...
-
Для решения поставленных задач используются следующие методы: 1) Иерархия пользователей будет определена при помощи построения UML диаграммы, для...
-
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляются два указателя: указатель на предыдущую запись в...
-
Этапы жизненного цикла БД включают: -Планирование БД - определяются принципы, задачи создания БД. -Проектирование БД. -Материализация БД -...
-
SPSS Modeler [29] - это программный комплекс, позволяющий строить прогностические модели и применять эту информацию при принятии решений на уровне...
-
Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...
-
ОПИСАНИЕ ПОДПРОГРАММ - Структуры и алгоритмы обработки данных
Процедуры начальной обработки базы данных: 1. void Read() - считывает базу данных и формирует индексный массив. 2. void PrintMas(void) - осуществляет...
-
Известно, что создание систем "с нуля" приводит к глобальным затратам компании на фонд оплаты труда, на поддержание созданного решения. К тому же, чем...
-
Информационная система крупной организации, как правило, представляет собой исторически сложившуюся совокупность отдельно работающих систем, которые...
-
Техническое обслуживание (сервис) не зависимо от принятой системы ТО может организовываться с использованием известных методов ТО. Метод технического...
-
Основные конструкции для разработки базы данных - База данных "Кинотеатр"
База данных - это организованная структура, предназначенная для хранения информации. Систему управления базой данных (СУБД) можно определить, как...
-
Рисунок 10. Архитектура программы В структуре программы обработки сложноструктурированных данных для научного эксперимента в ИИС "Шлаковые расплавы"...
-
В данном пункте представлено описание подключаемых к общей архитектуре ИС компании систем. Описание систем является справочной информацией для...
-
Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...
-
Как известно , необходимость интеграции нескольких информационных систем как внутри одной организации (системы являются подсистемами к историчной...
-
Теоретические аспекты поставленной задачи В этой части проекта будут объяснены этапы применения МКЭ для плоской фермы. В первой главе было рассмотрено...
-
Метод конечных элементов является численным методом для нахождения приближенных решений физических задач. В основе этого метода лежит разделение...
-
По результатам данного исследования необходимо выявить недостатки и ограничения существующих технологий интеграции. Для проведения исследования...
-
Конечно-элементный анализ широко применяется при решении задач механики деформируемого твердого тела, теплообмена, гидро - и газодинамики, электро - и...
-
Протокол проверки программы - Программирование алгоритмов линейных и циклических структур
1. Введем размерность массива N = 6 2. Заполним элементы массива X(i) следующими значениями: 12, 1.34, 8, 10, 17.5, 30 3. Получим следующие результаты:...
-
ДД-код Константа16 ДД-код Константа16 1111 1111 FF 0000 0000 00 0011 0101 35 1111 0100 F4 0101 0111 57 1001 1010 9A 1000 1101 8D 0000 0111 07 1000 0000...
-
Идея алгоритма Лемпеля-Зива, Алгоритм LZ77 - Анализ алгоритма Лемпеля-Зива
Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента....
-
Текущая инфраструктура компании совершенствуется, всегда появляются новые системны для подключения и внедрения. Инфраструктура построена на схеме...
-
Система - совокупность разнородных объектов, объединенных для достижения определенной цели. Системы могут различаться по элементам и целям....
-
Любой объект можно связать с набором процедур, исполняемых в строго определенные моменты. Процедура ( Procedure ) - это группа операторов языка....
-
Для иллюстрации последовательности проводимых работ приведем диаграмму Гантта данного проекта, на которой по оси Х изображены календарные дни от начала...
-
Постановление Правительства Российской Федерации №1119 "Об утверждении требований к защите персональных данных при их обработке в информационных системах...
-
Формулировка задания: Составьте программу подсчета числа тех гласных букв в слове X, что не используются в написании слова Z. Описание входных/выходных и...
-
Прогнозируемая оценка проекта после реализации единой шины данных как прослойки между всеми компонентами ИТ-ландшафта компании выполняется по методу...
-
Корпоративная интеграционная подсистема на базе IBM WebSphere Business Integration Message Broker [28] отвечает за выстраивание корпоративной...
-
В данном пункте представлено описание подключенных систем к общей инфраструктуре ИС компании. В случае IBM SPSS: Вследствие того, что сбор данных с...
-
Результаты проведенных экспериментов содержатся во внутреннем серверном файловом хранилище (Рис. 2). Представляют собой документы формата "*.DAT". В них...
-
Записи, множества, файлы - Структуры данных
Обобщением массива является комбинированный тип данных - запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись...
ОСНОВНЫЕ ИДЕИ И ХАРАКТЕРИСТИКИ ПРИМЕНЯЕМЫХ, МЕТОД СОРТИРОВКИ - Структуры и алгоритмы обработки данных