Сравнительный анализ Пирамидальной сортировки, шейкерной сортировки и многофазной сортировки

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Дагестанский государственный технический университет»

Кафедра ПОВТиАС

Пояснительная записка

к курсовой работе по дисциплине «Алгоритмы и структуры данных»

На тему:

«Сравнительный анализ Пирамидальной сортировки, шейкерной сортировки и многофазной сортировки»

        Выполнил:

ст. гр. У -433

3 курса ФКТВТиЭ

Гасанов И.Р.

Приняла: 

 Сулейманова О.Ш.

Махачкала 2016

Содержание

Введение        3

Постановка задачи        4

Анализ предметной области        5

Описание организации структур данных        6

Описание алгоритма        7

Формальное описание входных и выходных данных        13

Описание диалога        14

Описание процедур и функций        15

Результаты        16

Заключение        17

Литература        18

Приложение 1        19

Введение

Сортировка – это процесс перегруппировки заданного множества объектов в некотором определённом порядке. Цель сортировки: облегчить поиск элементов. Существует множество методов сортировки, каждый из которых имеет свои достоинства и недостатки. Выбор алгоритма зависит от структуры обрабатываемых данных. Алгоритмы сортировки имеют большое прикладное значение, они интересны и сами по себе. Это достаточно глубоко исследованная область информатики используется в информационно-поисковых системах, в военном и банковском деле. Кроме общенаучного интереса к алгоритмам сортировки, в каждом алгоритме интересно оценить и его так называемую сложность. Под сложностью понимается максимальное число элементарных шагов алгоритма. На примерах сортировок можно показать, как путём усложнения алгоритма, хотя под рукой и есть уже очевидные методы, можно добиться значительного выигрыша в эффективности. Методы сортировки можно разбить на два класса – сортировку массивов и сортировку файлов. Иногда их называют внутренней и внешней сортировкой, так как массивы хранятся в быстрой, оперативной, внутренней памяти машины со случайным доступом, а файлы размещаются в более медленной, но и более ёмкой внешней памяти.

Цель сортировки – ускорение поиска данных. Различают сортировку массивов и сортировку файлов (внешние сортировки).

Алгоритмы сортировки классифицируют на алгоритмы сортировки объектов с произвольным доступом (массивы и дисковые файлы произвольного доступа) и алгоритмы сортирующие последовательные объекты (файлы на лентах и дисках).

        В данной работе рассмотрены описания пирамидальной сортировки, многофазной и шейкерной сортировки.

Постановка задачи

Рассмотреть, сравнить и реализовать следующие виды сортировок:

1. Пирамидальная сортировка;
2. Многофазная сортировка;
3. Шейкерная сортировка.

Анализ предметной области

На практике очень часто попадаются задачи, в которых необходимо отсортировать те или иные данные. Учитывая, что в реальности вычислительные возможности ограничены и наступает необходимость сортировать данные как можно быстрее, были разработаны множество видов сортировок. Одни сортировки быстрее сортируют небольшие объемы данных, другие позволяют выиграть при больших объемах данных. Чтобы определить какие виды сортировка необходимы в данный момент необходимо сравнить разные виды сортировок.

Описание организации структур данных

В данной курсовой работе в качестве примера применены массивы типа int в качестве структур данных.

Описание алгоритма

 Пирамидальная сортировка

Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце.