jghjgj
Информация о работе
Подробнее о работе
Алгоритмы сортировки
- 29 страниц
- 2016 год
- 124 просмотра
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Оглавление
Введение 2
1. Постановка задачи на исследование 3
1.1. Выбор программного обеспечения для реализации программы 3
1.2. Интерфейс программы 4
2. Теоретическое исследование алгоритмов 5
2.1. Анализ сложности алгоритмов 5
2.2. Сортировка методом «пузырька» 6
2.3. Быстрая обменная сортировка 9
3. Разработка подхода к оценке эффективности алгоритмов 12
4. Реализация программы. 13
4.1 Реализация метода быстрой сортировки 13
4.2 Реализация метода «пузырька» 15
4.3. Тестирование программ 17
4.4. Проведение экспериментов для сравнительной оценки эффективности алгоритмов 18
4.5. Анализ эффективности 23
Заключение 27
Список литературы 28
Приложение 29
1.1. Выбор программного обеспечения для реализации программы
Для реализации алгоритмов сортировок был выбранязык программирования высокого уровня – С++. C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения включает созданиеоперационных систем, разнообразных прикладных программ, драйверов устройств, приложений для встраиваемых систем, и высокопроизводительных серверов.Он является одним из наиболее используемых языков программирования, с помощью которого можно написать программы, функционирующей в операционной системеWindows. MicrosoftVisualStudio является отличной средой для разработки приложений и достойных альтернатив этому средству разработки практически нет. [4,5].
MicrosoftVisualStudio [4,5]- набор инструментов, с помощью которых процесс реализации инновационных замыслов разработчика легко воплощается в жизнь.
...
2.1. Анализ сложности алгоритмов
Целью анализа трудоёмкости алгоритмов является нахождение оптимального алгоритма для решения данной задачи. В качестве критерия оптимальности алгоритма выбирается трудоемкость алгоритма.Трудоемкость алгоритма – это количествоопераций сравнения, обмены, сдвиги, повторения цикла и т.п. от объема (размерностей) обрабатываемых данных.
Трудоемкость может зависеть от входных данных. Поэтому оценка трудоемкости дается для лучшего и худшего случая, а также в среднем Tmin, Tmax, Tср. Свойство программы – иметь различную трудоемкость для разных данных, называетсячувствительностью к данным.Трудоёмкость многих алгоритмов может в той или иной мере зависеть от всех перечисленных выше факторов.
Одним из упрощенных видов анализа, используемых на практике, является асимптотический анализ алгоритмов.Асимптотическиманализомназываетсяанализсравнения затрат времениалгоритмов, выполняемыхрешениеэкземпляранекоторойзадачи, при большихобъемахвходныхданных.
...
2.2. Сортировка методом «пузырька»
Сортировка методом пузырька– простой алгоритм сортировки. Для понимания и реализации этот алгоритм– простейший, но эффективен он лишь для небольших массивов.
Сложность алгоритма– понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Сложность алгоритма в нашем случае: O(n2).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Этот алгоритм основан на принципе сравнения и обменасоседних пар до тех пор, пока не будет получен отсортированныймассив. Пример сортировки методомпузырька вы можете увидеть на рисунке 2.
...
2.3. Быстрая обменная сортировка
Быстрая обменнаясортировка, часто называемая qsort - широко известный алгоритмсортировки, разработанныйанглийскиминформатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году[3,4].
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем обменов при упорядочении элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Алгоритм быстрой сортировки является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена. Его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка» известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.
...
4.1 Реализация метода быстрой сортировки
Для того, чтобы запрограммировать данный алгоритм сортировки, представим его сначала в виде блок-схемы для более наглядного отображения его функционирования
i, j- счетчики;
tmp–переменная для хранениявременных данных;
a- массив элементов;
pivot–средний опорный элемент;
left,right – переменные хранящие правую и левую сторону массива
Рисунок 3 Блок схема быстрой сортировки
По данной блок схеме реализуем программный код на С++
void quickSort(int** a, int left, int right) {
int i = left, j = right;
int tmp;
int pivot = (*a)[(left + right) / 2];
/* partition */
while (i <= j) {
while ((*a)[i] < pivot)
i++;
while ((*a)[j] > pivot)
j--;
if (i <= j) {
tmp = (*a)[i];
(*a)[i] = (*a)[j];
(*a)[j] = tmp;
i++;
j--;
}
};
/* recursion */
if (left < j)
quickSort(a, left, j);
if (i < right)
quickSort(a, i, right);
}
4.2 Реализация метода «пузырька»
Для того, чтобы запрограммировать данный алгоритм сортировки представим его сначала в виде блок-схемы для более наглядного отображения его функционирования
i-счетчик;
tmp–переменная для хранениявременных данных;
ext – переменная использующая как знак того, что сортировка закончена и можно выходить;
a- массив элементов;
l_arr- количество элементов в массиве arr;
Рисунок 4 Блок схема сортировки «Пузырьком»
По данной блок схеме реализуем программный код на С++
void bubble(int **a, int l_arr)
{
int tmp = 0;
bool ext = false;
while (!ext)
{
ext = true;
for (int i = 0; i < (l_arr - 1); i++)
if ((*a)[i] > (*a)[i + 1])
{
tmp = (*a)[i];
(*a)[i] = (*a)[i + 1];
(*a)[i + 1] = tmp;
ext = false;
}
}
}
4.3.
...
4.4. Проведение экспериментов для сравнительной оценки эффективности алгоритмов
Экспериментыбыли проведены на компьютере с 64 битной архитектурой, процессором Pentium(R) 2.0 Ghz, оперативной памятью равной 4Гб, под управлением операционной системыWindows8.
Тестирование над 5000 элементами:
Рисунок 8Эксперимент 1
Тестирование над 10000 элементами:
Рисунок 9Эксперимент 2
Тестирование над 15000 элементами:
Рисунок 10 Эксперимент 3
Тестирование над 20000 элементами:
Рисунок 11 Эксперимент 4
Тестирование над 25000 элементами:
Рисунок 12 Эксперимент 5
Тестирование над 30000 элементами:
Рисунок 13 Эксперимент 6
Тестирование над 35000 элементами:
Рисунок 14 Эксперимент 7
4.5.
...
4.5. Анализ эффективности
Отобразим на графике зависимость среднего времени сортировки от числа сортируемых элементов:
Рисунок 15 Случайное заполнение
Рисунок 16 Обратное заполнение
Рисунок 17 Специальное заполнение
Рисунок 18 Среднее значение
Рисунок 19 Сравнение сложностей
Результаты вычислительных экспериментов показывают, что общее время быстрой обменной сортировки значительно меньше, чем методом пузырька.
Следовательно, быстрая обменная сортировка является наиболее эффективной, чем сортировка методом пузырька. Следовательно, можно сделать вывод, что сортировка «Пузырьком» не имеет практического применения и считается учебным алгоритмом.
Также следует отметить, что время сортировки зависит от варианта заполнения массива. Например, быстрая обменная сортировка лучше себя показывает, когда значения элементов массива разбросаны в случайном порядке и хуже всего, когда массив заполнен в обратном порядке.
...
Заключение
В ходе проделанной работы были исследованы два алгоритма сортировки, которые используются наиболее часто в разных сферах практической деятельности. Используя написанную нами программу, мы выяснили, что алгоритм быстрой сортировки показал лучший результат по времени в сравнении с алгоритмом пузырька. Сортировка методом пузырька показала значительно более долгое выполнение алгоритма. Также график сравнения сложностей показал, что сложность сортировки «Пузырьком» значительно превосходит сложность алгоритма быстрой сортировки, что подтверждает полученные нами данные.
Разработан подход к сравнению алгоритмов и написаны функции для сортировок, которые заполняют массив различными способами, а также сами сортировки и подсчета промежутков времени работы сортировок.
Были построеныграфики и диаграммы, где отображенызависимость среднего времени сортировки от числа сортируемых элементов.
...
1. Д. Либерти С++ за 21 день – М.: 2007
2. Коплиен Дж. Программирование на С++, –изд. "Питер ", 2005.
3. Роберт Седжвик. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных.–изд. "Вильямс", 2006.
4. Павловская,Т.АПрограммирование на языке высокого уровня. – изд. "Питер", 2004.
5. Интерактивный учебник по VisualStudio[Электронный ресурс]. – Режим доступа: https://msdn.microsoft.com/ru-ru/library/bb514232 (дата обращения: 23.05.2015).
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
