Экспериментальное исследование алгоритмов быстрой и пирамидальной сортировок
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное
автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный
университет»
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
Кафедра математического обеспечения и
администрирования информационных систем
КУРСОВОЙ ПРОЕКТ
По дисциплине «Структуры и алгоритмы
компьютерной обработки данных»
по образовательной программе
подготовки бакалавров
по направлению 02.03.03
«Математическое обеспечение и администрирование информационных систем» программ
«Технология программного обеспечения»»
ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ
АЛГОРИТМОВ БЫСТРОЙ И ПИРАМИДАЛЬНОЙ СОРТИРОВОК
Студент гр. Б8204 Нечаев Павел Владимирович
Руководитель: К.т.н. С.Н. Остроухова
г. Владивосток
2015 г.
Оглавление
Введение
. Требования к данным в экспериментальном исследовании
. Требования к данным в генерации последовательности
. Функциональные требования для экспериментального
исследования
. Функциональные требования для генерации последовательности
. Требования к удобству использования КП
. Требования к мобильности КП
7. Сценарий диалога программы с пользователем
. Экспериментальные исследования
. Дополнительные исследования
Вывод
Список литературы
Введение
На сегодняшний день существует множество алгоритмов сортировки и их
модификаций. Каждый алгоритм сортировки имеет свои преимущества и недостатки и
достоин тщательного рассмотрения.
Двумя самыми быстрыми алгоритмами внутренней сортировки на сегодняшний
день являются алгоритмы быстрой и пирамидальной сортировки. У этих алгоритмов
есть 2е общие черты:
1. Оба имеют асимптотически наилучшую возможную сложность O(NlogN), где N -
длина сортируемого массива.
2. Оба неэффективны для малого числа сортируемых элементов.
Цель моего курсового проекта:
Сравнить производительность алгоритмов быстрой и пирамидальной
сортировок, сравнить полученные результаты с теоретическими данными.
Задачи:
) Разработать компьютерную программу(КП) для экспериментального
исследования алгоритмов быстрой и пирамидальной сортировок.
) Провести экспериментальные исследования.
) Проанализировать результаты экспериментальных исследований,
полученные при помощи данной КП; Сравнить с теор. данными.
Назначение
КП
В рамках курсового проекта была создана компьютерная программа, которая
позволяет наглядно оценить производительность двух алгоритмов: пирамидальной и
быстрой сортировок, а так же сравнить их между собой на разных типах
последовательностей. Благодаря данной программе можно будет понять на каких
типах последовательностей более оптимально применять тот или иной алгоритм.
.
Требования к данным в экспериментальном исследовании
) Входные данные:
список файлов, каждый из которых:
Ø является текстовым файлом с расширением .txt, в котором должна быть записана
ровно 1 последовательность в первой строке. Во второй строке записан один из
видов последовательности: "Возрастающая", "Убывающая",
"Рандомная", "По формуле".
В третьей строке записан размер последовательности 
[1;10000];
Ø Все элементы данной последовательности - целые числа, в
качестве разделяющего элемента выступает пробел. Количество элементов в файле
не может превышать 10000;
Ø имеет свое уникальное имя.
b) Выходные данные - 3 гистограммы.
b.1) На первой гистограмме будет отображена зависимость времени работы
алгоритмов быстрой и пирамидальной сортировок..2) На второй гистограмме
будет отображена зависимость числа сравнений, которые произвели алгоритмы
быстрой и пирамидальной сортировок..3) На третьей гистограмме будет
отображена зависимость числа обменов, которые произвели алгоритмы быстрой и
пирамидальной сортировок.
.
Требования к данным в генерации последовательности
) Входные данные
a.1) Вид последовательности может быть следующих типов:
Ø Возрастающая
Ø Убывающая
Ø Рандомная
Ø По формуле
a.2) Число элементов в последовательности не должно превышать 10000 и быть не
меньше 1;
a.3) Минимальное и максимальное значение элементов последовательности должно
быть не меньше 0 и не больше 32768..4) Минимальное значение
элемента последовательности не должно превышать максимальное значение.
a.5) Первый элемент последовательности должен быть не меньше 0 и не больше
32768.
a.6) Формула, состоящая из выражений вида:. число [1;32768]
ii. x. Формула + (-, *, /)
Формула
iv. Mod(Формула, Формула) - остаток от деления. (Формула). Суперпозиция
Формул.7) Имя файла, в который требуется сохранить генерируемую
последовательность.) Выходные данные
Файл с расширением .txt со
сгенерированной последовательностью и информацией о ней.
3.
Функциональные требования для экспериментального исследования
1. КП должна уметь выполнять алгоритмы быстрой и пирамидальной
сортировок на выбранных файлах, если совпадает их длинна или тип
последовательности, в противном случае выводить сообщение о несоответствии
файлов.
. КП должна уметь засекать время работы быстрой и пирамидальной
сортировки для сортируемых последовательностей; КП должна уметь по полученным
данным строить график I.b.1;
. КП должна уметь считать число сравнений во время работы КП на
заданных последовательностях и по полученным данным строить график I.b.2;
. КП должна уметь считать число обменов во время работы КП на
заданных последовательностях и по полученным данным строить график I.b.3;
4.
Функциональные требования для генерации последовательности
1. КП должна позволять вводить:
· Вид последовательности
· Диапазон чисел в генерируемой последовательности (минимальное
и максимальное значение последовательности), в случае если выбран тип последовательности не
"По формуле".
· Первый элемент последовательности, а так же формулу(см. II. a. a.6). При этом, i-й элемент будет получаться из (i-1)-го вычислением выражения формулы, в которой все "x" будут заменены на i-й элемент.
· Число элементов в последовательности
. КП должна уметь генерировать заданную последовательность
выбранного вида.
4. КП должна предоставлять предварительный просмотр сгенерированной
последовательности в виде списка, в случае, когда размер последовательности не
превышает 500 элементов.
. КП должна сохранять сгенерированную последовательность в файл с
заданным пользователем именем.
. КП должна заменять файл с аналогичным именем при сохранении
последовательности в файл.
5.
Требования к удобству использования КП
a) КП должна быть
предназначена для любого человека, который имеет навык работы на компьютере и
понимает все 5 типов последовательностей, а так же умеет вводить формулы(см.
II. a. a.6).) КП должна выдавать все сообщения на русском
языке, за исключением некоторых имен файлов и папок, а так же общеиспользуемых
английских слов.) Интерфейс КП должен быть понятен.) Процедура
запуска КП должна быть понятна и проста для пользователя.
6.
Требования к мобильности КП
КП должна быть переносимой без изменений из одной среды в другую в рамках
Windows 7/8 и их 32-х и 64-х разрядные
версии.
Архитектура
КП
генерация
последовательность программа пользователь
Основной модуль предоставляет возможность выбора файлов для проведения
эксперимента, проведения эксперимента на выбранных файлах, а так же перехода к
окну генерации последовательностей.
Модуль генерации последовательностей позволяет создавать
последовательность типа вид последовательности с количеством элементов
равным Число элементов в последовательности, в диапазоне от Минимального
значения до максимального значения в случае, если вид последовательности
не "По формуле". И позволяет создавать последовательность типа
"По формуле" с количеством элементов равным Число элементов
в последовательности, с первым элементом Первый элемент
последовательности по формуле Формула (см. II. a. a.6, V. a).
Модуль вывода результатов строит гистограммы трех видов: II.b.1, II.b.2, II.b.3.
7. Сценарий
диалога программы с пользователем
Из основного окна (рис.1) возможен переход к окну «генерация» (рис.2),
выбор файлов для эксперимента, а также проведение эксперимента и переход к
модулю вывода результатов (рис. 4).
Основное окно состоит из трех кнопок: "Выбрать файлы",
"Провести эксперимент", "Генерация".
Рис. 1 «Основное окно»
Кнопка "Выбрать файлы" - стандартное диалоговое окно с
автоматически заданной директорией. Все что нужно сделать - выбрать файлы для
эксперимента. Для точности эксперимента изменять директорию не рекомендуется.
При нажатии кнопки "Провести эксперимент", если файлы были
выбраны корректно (III. 1, I. a ), пользователь увидит окно "Результат", в
противном случае будет выведено сообщение об ошибке.
Окно «Результат» (рис.4) позволяет пользователю увидеть результат
эксперимента в виде графиков трех видов: II.b.1, II.b.2, II.b.3.
Рис. 4 «Результат»
Пользователь может вызвать несколько окон «Результат» и провести
эксперименты параллельно.
Окно «Генерация» (рис.2) состоит из шести контейнеров: «Тип
последовательности», «Число элементов», «Мин. Значение», «Макс. Значение», «Имя
файла», кнопки: «Генерация».
Рис. 2 «Генерация »
Контейнер «Тип последовательности» содержит 4 пункта:
«Возрастающая», «Убывающая», «По формуле», «Рандомная», каждый из которых
позволяет задать тип генерируемых последовательностей.
Контейнер «Размер последовательности» позволяет задать число
элементов в последовательности.
Контейнер «Мин. Значение» позволяет задать минимальный элемент
последовательности.
Контейнер «Макс. Значение» позволяет задать максимально возможное
значение элемента последовательности, при этом если «Мин. Значение» будет
больше «Макс. Значение», тогда при нажатии кнопки "Генерация"
пользователь получит сообщение об ошибке.
При выборе типа последовательности «По формуле», окно генерация меняет
свой вид. Контейнеры «Мин. Значение» и «Макс. Значение» заменяются
контейнерами «Первый элемент» и «Формула» (рис. 3).
Рис. 3 «Генерация (с формулой)»
Контейнер «Первый элемент» позволяет ввести первый элемент
генерируемой последовательности.
Контейнер «Формула» позволяет ввести необходимую формулу для
генерации последовательности.
Если при нажатии кнопки «Генерация» не был выбран тип последовательности
или пользователь ввел некорректные данные, будет выведено сообщение об ошибке.
Если все данные были введены корректно, пользователь увидит окно, в котором
требуется подтвердить сохранение файла с последовательностью и информацией о
ней, если её размер меньше 500 элементов - последовательность будет выведена в
этом окне, в противном случае в этом окне будет информация о том, что размер
последовательности слишком велик, чтобы выводить ее на экран,. Сгенерированный
файл появятся в директории с самой КП. Директорию, где находятся
сгенерированные последовательности, КП задает автоматически. Если пользователь
не подтвердил сохранение файла, тогда пользователь вернется к окну «Генерация».
8.
Экспериментальные исследования
Для анализа были выбраны следующие типы последовательностей:
· Возрастающая
· Убывающая
· Чередующаяся
· Рандомная
В ходе эксперимента было сформировано 4 набора последовательностей.
Последовательности разделили на 4 группы по 1 набору каждого типа. Таким
образом, последовательности из каждой группы будут иметь длину от 100 до 10000
соответственно. Количество последовательностей в каждом наборе неизменно.
· Результаты
эксперимента для первой группы
Результаты представлены на рисунке 5 для возрастающих
последовательностей.
Рис.5 Результат эксперимента для возрастающих последовательностей
Метод быстрой сортировки для возрастающих последовательностей работает
намного быстрее, так как алгоритм быстрой сортировки сразу же приступает к
сравнению элементов массива, в то же время алгоритму пирамидальной сортировки
требуется время на построение пирамиды. Так же можно сказать о том, что все три
параметра увеличиваются с увеличением числа элементов в исходной
последовательности.
· Результаты
эксперимента для второй группы
Результаты представлены на рисунке 6 для убывающих последовательностей.
Рис.6 Результат эксперимента для убывающих последовательностей
Для убывающих последовательностей результаты разнятся несколько меньше,
чем для возрастающих последовательностей. Количество сравнений каждого из
алгоритмов очень близки. Аналогично случаю с возрастающими
последовательностями, все три параметра увеличиваются с увеличением числа
элементов в исходной последовательности.
· Результаты
эксперимента для третьей группы
Результаты представлены на рисунке 7 для чередующихся
последовательностей.
Рис.7 Результат эксперимента для чередующихся последовательностей
Для чередующихся последовательностей можно отметить, что оба алгоритма
имеют схожее число обменов на каждой из последовательностей. Однако, быстрая
сортировка совершает меньше сравнений, в следствие чего получается третий
график - Затраченное время. Следует заметить, что при малых размерах
последовательности (около 50 элементов), результаты каждого из графиков
отличаются не более чем в два раза.
· Результаты
эксперимента для четвертой группы
Результаты представлены на рисунке 8 для рандомных последовательностей.
Рис.8 Результат эксперимента для рандомных последовательностей
Рандомные последовательности - последовательности, которые чаще всего
нуждаются в сортировке. Из результатов эксперимента для четвертой группы видно,
что на таких последовательностях быстрая сортировка работает в несколько раз
быстрее, проводя меньше сравнений и обменов.
9.
Дополнительные исследования
Все предыдущие эксперименты показали, что быстрая сортировка работает
быстрее пирамидальной. Однако существуют такие последовательности, на которых
быстрая сортировка будет работать медленнее. Возьмем следующую
последовательность: "0 1 2 3 4 5 6 7 8 9 2 5 1 6 3 7 0 8 4 0 1 2 3 4 5 6 7
8 9 2 5 1 6 3 7 0 8 4 0 1 2 3 4 5 6 7 8 9 2 5 1 6 3 7 0 8 4 0 1 2 3 4 5 6 7 8 9
2 5 1 6 3 7 0 8 4" и проведем эксперимент. Результаты эксперимента
представлены на рисунке 9.
Рис.9 Результат эксперимента для худшего случая для быстрой сортировки
Из результатов эксперимента видно, что на данной последовательности
быстрая сортировка работает несколько медленнее пирамидальной, несмотря на то,
что быстрая сортировка совершает меньше обменов и сравнений; это происходит
из-за того, что быстрая сортировка организована рекурсивно. Это будет
происходить для последовательностей, таких что на каждом этапе массив будет
разделяться на вырожденный подмассив из одного опорного элемента и на подмассив
из всех оставшихся элементов.
Вывод
В рамках данного проекта была создана КП, выполняющая генерацию
последовательностей и эксперимент над сгенерированными последовательностями.
На основе всех четырех основных экспериментов (рис. 5, 6, 7, 8) можно
сделать следующий вывод: метод быстрой сортировки в общем случае работает в
несколько раз быстрее метода пирамидальной сортировки, причем время работы
метода пирамидальной сортировки значительно увеличивается с увеличением
количества элементов.
На основе дополнительного эксперимента (рис. 9) можно сделать следующий
вывод: существуют такие типы последовательностей, на которых метод
пирамидальной сортировки работает быстрее метода быстрой сортировки, причем с
увеличением числа элементов такой последовательности время работы существенно
увеличивается.
На основе выше приведенных выводов можно утверждать, что метод быстрой
сортировки является более эффективным, чем алгоритм пирамидальной сортировки.
Однако, существуют последовательности, на которых быстрая сортировка работает
несколько медленнее пирамидальной.
Таким образом, при выборе алгоритма сортировки для конкретной предметной
области большое значение имеют размеры сортируемых последовательностей и типы
последовательностей.
Список
литературы
1. Вирт Н. Систематическое программирование. Введение:
учебник для научных работников, преподавателей, аспирантов и студентов,
специализирующихся по математическому анализу ЭВМ - М: Мир, 1977.
. Быстрая сортировка [Электронный ресурс] - Режим
доступа: http://kvodo.ru/quicksort.html [25.06.2015]
. Реализации алгоритмов: Быстрая сортировка
[Электронный ресурс] - Режим доступа: http://cybern.ru/qsort-csharp.html
[19.06.2015]
. Шилдт Г. C# 4.0: полное руководство. :Пер. с англ. -М. : ООО “И.Д. Вильямс” , 2001.
- 1056 с.
. Пирамидальная сортировка [Электронный ресурс] -
Режим доступа: http://cybern.ru/heapsortcpp.html [29.06.2015]
. Пирамидальная сортировка [Электронный ресурс] -
Режим доступа: http://trubetskoy1.narod.ru/alg/pyramidsort.html [01.07.2015]