Пр_4. Практическая работа Строгие методы сортировки и их реализация. Улучшенные методы сортировки и их реализация
 Скачать 426.64 Kb.
|
|
Естественность поведения – это один из параметров трудоемкости алгоритма, которой указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Ключ сортировки – это атрибут (или несколько атрибутов), по значению которого определяется порядок элементов во множестве. Опорный (ведущий) элемент – это некоторый элемент массива, который выбирается определенный образом, и относительно которого происходит сравнение и перемещение элементов между подмножествами массива. Память – один из параметров трудоемкости алгоритма, который характеризует размер выделяемой дополнительной памяти под временное хранение данных. Пирамида (сортирующее дерево, двоичная куча) – это двоичное дерево с упорядоченными листьями, в корне которого расположен максимальный или минимальный элемент. Просеивание – это построение новой пирамиды посредством спуска вниз элемента из вершины дерева в соответствии с ключом сортировки Слияние – это объединение двух или более упорядоченных массивов в один упорядоченный. Сортировка слиянием – это одна из разновидностей алгоритмов быстрых сортировок, основанная на слиянии подмножеств массива. Сортировка Хоара – это одна из разновидностей быстрых сортировок, основанная на упорядочивании подмножеств массива относительно опорных элементов. Сортировка Шелла – это алгоритм внутренней сортировки, основанный на сравнении и перемещении пар значений, расположенных сначала достаточно далеко друг от друга в упорядочиваемом наборе данных, с дальнейшим сокращением расстояний между ними. Устойчивость – это один из параметров трудоемкости алгоритма, который характеризует то, что сортировка не меняет взаимного расположения равных элементов. Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память. Двухпутевое слияние – это сортировка, в которой данные распределяются на два вспомогательных файла. Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Длина серии – это количество элементов в серии. Естественное слияние – это сортировка, при которой всегда сливаются две самые длинные из возможных серий. Многопутевое слияние – это сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов. Несбалансированное слияние – это естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга более чем на единицу. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну. Простое слияние – это одна из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла. Сбалансированное слияние – это естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов доступных в данный момент. Фаза – это действия по однократной обработке всей последовательности элементов. Краткие итоги Сортировка является одной из фундаментальных алгоритмических задач программирования. Практически каждый алгоритм сортировки можно разбить на 3 части: сравнение, определяющее упорядоченность пары элементов; перестановку, меняющую местами пару элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. Для оценки трудоемкости алгоритмов сортировки используются параметры: время сортировки, дополнительная память, устойчивость и естественность поведения По сфере применения алгоритмы сортировок классифицируются на алгоритмы внутренних и внешних сортировок. Бинарная пирамидальная сортировка является алгоритмом внутренней сортировки, основанном на построении пирамиды и просеивании элементов из ее вершины методом спуска вниз в соответствии с ключом сортировки Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым. Поведение неестественно. Данная сортировка на почти отсортированных массивах работает также долго, выигрыш ее получается только на больших n. Сортировка Шелла является алгоритмом внутренней сортировки, основанном на сравнении и перемещении пар значений, расположенных сначала достаточно далеко друг от друга в упорядочиваемом наборе данных, с дальнейшим сокращением расстояний между ними. Сортировка Шелла является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Сортировка Хоара является одной из разновидностей быстрых сортировок, основанная на упорядочивании подмножеств массива относительно опорных элементов. Эффективность быстрой сортировки в значительной степени определяется правильностью выбора опорных элементов при формировании блоков. Сортировка слиянием является одним из самых простых алгоритмов сортировки среди быстрых алгоритмов, который может быть эффективно использован для сортировки связанных списков. Недостаток алгоритма сортировки слиянием заключается в том, что он требует дополнительную память размером порядка n, не гарантирует сохранение порядка элементов с одинаковыми значениями. Его временная сложность всегда пропорциональна O(n log n). Быстрая сортировка является наиболее эффективным алгоритмом из всех известных методов сортировки, но все усовершенствованные методы имеют один общий недостаток – невысокую скорость работы при малых значениях n. Внешние сортировки применяются к данным, которые хранятся во внешней памяти. Внешние сортировки применяются, если объем сортируемых данных превосходит допустимое место в ОЗУ. Внешние сортировки, по сравнению с внутренними, характеризуются проигрышем по времени за счет обращения к внешним носителям. К наиболее известным алгоритмам внешних сортировок относятся: сортировки слиянием (простое слияние и естественное слияние); улучшенные сортировки (многофазная сортировка и каскадная сортировка). Алгоритмы внешних сортировок отличаются по реализации числом фаз и путей. Простое слияние является одной из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге. Естественное слияние является сортировкой, при которой всегда сливаются две самые длинные из возможных серий. Число чтений или перезаписей файлов при использовании метода естественного слияния будет не хуже, чем при применении метода простого слияния, а в среднем – даже лучше. Однако в данном методе увеличивается число сравнений за счет распознавания концов серий. Задание на Практическую работу При выполнении Практической работы для каждого задания требуется написать программу, которая получает на входе числовые данные, выполняет генерацию и вывод массива указанного типа в зависимости от постановки задачи. В каждой задаче необходимо выполнить сортировку данных и реализовать один из алгоритмов: бинарной пирамидальной сортировки, сортировки по методу Шелла, быстрой сортировки Хоара и сортировки слиянием в виде отдельных функций. Ввод данных осуществляется с клавиатуры или из файла с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные является диапазон используемого числового типа данных в языке программирования и максимально допустимый размер объявляемого одномерного массива. Задания к Практической работе. Выполните приведенные ниже задания. На основании приведенных в Практической работе 4 функций реализуйте алгоритмы сортировок. Даны два целочисленных файла, упорядоченных по возрастанию. Сформировать третий файл на основе данных, который также упорядочен и представляет операцию с элементами исходных файлов: объединение (содержит числа, принадлежащие хотя бы одному из множеств); перечисление (числа, принадлежащие обоим множествам); разность (числа, принадлежащие первому множеству, но не второму); симметричную разность (объединение разностей множеств). Заданы N (N<=5000) попарно различных длин отрезков. Вычислить количество способов, которыми из отрезков можно сложить треугольник. Дана целочисленная квадратная матрица размером n. Упорядочить значения так, чтобы a11<=a12<=<=a1n<=a21<=a22<=<=a2n<=<=an1<=an2<=<=ann. Дан целочисленный массив. Выполните проверку уникальности. Удалите из массива повторные вхождения чисел. На основании приведенной в Практической работе 4 функции реализуйте программу, в которой выполняется алгоритм внешней сортировки двухпутевым двухфазным простым слиянием. На основании приведенной в Практической работе 6 функции реализуйте программу, в которой выполняется алгоритм внешней сортировки двухпутевым двухфазным естественным слиянием. Дан полный перечень всех стран, который включает в себя: название, континент, столицу, площадь, численность населения. Указать сведения о государствах заданного континента в порядке возрастания численности населения. Использовать двухпутевое однофазное простое слияние. Даны сведения о химических веществах, которые включает в себя: класс вещества, название вещества, молекулярная масса вещества. Упорядочить по возрастанию молекулярных масс все вещества указанного класса. Использовать двухпутевое двухфазное естественное сбалансированное слияние. В файле хранится последовательность русских слов. Упорядочить ее в алфавитном порядке. Использовать внешнюю сортировку. Учесть, что порядок кодов букв русского алфавита не соответствует порядку букв в алфавите. Указания к выполнению работы. Каждое задание необходимо решить в соответствии с изученными алгоритмами внутренних сортировок: бинарной пирамидальной сортировки, сортировки по методу Шелла, быстрой сортировки Хоара и сортировки слиянием. Рекомендуется воспользоваться материалами Практической работы 4, где подробно рассматриваются описание используемых в работе алгоритмов, примеры их реализации на языке С++. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, используя функции. Этапы решения сопроводить комментариями в коде. В отчете следует отразить разработку и обоснование математической модели решения задачи и примеры входных и выходных файлов. Следует реализовать каждое задание в соответствии с приведенными этапами: изучить словесную постановку задачи, выделив при этом все виды данных; сформулировать математическую постановку задачи; выбрать метод решения задачи, если это необходимо; разработать графическую схему алгоритма; записать разработанный алгоритм; разработать контрольный тест к программе; отладить программу; представить отчет по работе. Требования к отчету. Отчет по Практической работе должен соответствовать следующей структуре. Титульный лист. Словесная постановка задачи. В этом подразделе проводится полное описание задачи. Описывается суть задачи, анализ входящих в нее физических величин, область их допустимых значений, единицы их измерения, возможные ограничения, анализ условий при которых задача имеет решение (не имеет решения), анализ ожидаемых результатов. Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке. Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Листинг программы. Подраздел должен содержать текст программы на языке программирования. Контрольный тест. Подраздел содержит наборы исходных данных и полученные в ходе выполнения программы результаты. Выводы по Практической работе. Ответы на контрольные вопросы. Контрольные вопросы Чем можно объяснить многообразие алгоритмов сортировок? Почему на данный момент не существует универсального алгоритма сортировки? Как соблюдение свойств устойчивости и естественности влияет на трудоемкость алгоритма сортировки? За счет чего в алгоритмах быстрых сортировок происходит выигрыш при выполнении операций сравнения и перестановок? Какие из перечисленных алгоритмов наиболее эффективны на почти отсортированных массивах: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара? За счет чего происходит выигрыш? Почему алгоритмы быстрых сортировок не дают большого выигрыша при малых размерах массивов? В чем преимущества и недостатки по отношению друг к другу следующих алгоритмов сортировок: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара? Как определить, какому алгоритму сортировки отдать предпочтение при решении задачи? Чем обусловлено использование алгоритмов внешних сортировок? Как расходуется ОЗУ при использовании различных алгоритмов внешних сортировок? Каким слиянием, простым или естественным, эффективнее объединять два упорядоченных по общему ключу файла? Ответ обоснуйте. Какие еще факторы, кроме числа фаз и путей, следует учитывать при анализе эффективности алгоритмов внешних сортировок? Как определить, какому алгоритму внешних сортировок отдать предпочтение при решении задачи? |