Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра комплексной информационной безопасности электронно- вычислительных систем (КИБЭВС)

Оценка алгоритмической сложности

Отчет по лабораторной работе №1

по дисциплине «Технологии и методы программирования»

Выполнил Студент гр. 739-1 Климанов М. Д.

. .2021

Принял

Доцент кафедры КИБЭВС

Лунёва Е. Е.

. .2021

Томск 2021

Содержание

1 Введение 3

1. Сортировка «Расческа» 4

2. Сортировка Шелла 10

3. Быстрая сортировка 16

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

5. Выявление лучшего и худшего результата работы каждой сортировки 29

3 Заключение 34

Приложение А 35

Приложение Б 40

Приложение В 44

Приложение Г 49

1 Введение

Цель работы: оценить алгоритмическую сложность сортировок, таких как: сортировка «Расческа», сортировка Шелла, быстрая сортировка, пирамидальная сортировка.

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

Необходимо оценить сложности четырех алгоритмов:

• сортировка «Расческа»;

• сортировка Шелла;

• быстрая сортировка;

• пирамидальная сортировка.

Шаги 1-3 выполнить для массивов длины: 1, 2, 3, 4, 5, 10, 15, 20, 25, 30,

50, 75, 100, 250, 500.

1. Сгенерировать 1000 массивов заданной длины.

2. Отсортировать все массивы исследуемым алгоритмом сортировки и подсчитать количество операций, выполненных для их

сортировки, а также время, затраченное на сортировку всех массивов.

3. Вычислить среднее время и среднее количество операций произведенных для сортировки массива заданной длины.

4. Построить графики зависимостей количества операций от длины массива.

5. Построить графики зависимости времени от длины массива.

6. На графиках из пунктов 4 и 5 также построить графики зависимостей: y=n, y=n*log(n), y=n², y=n³.

7. Сделать выводы об алгоритмической сложности каждого алгоритма.

8. Для каждой рассмотренной сортировки сгенерировать лучший и худший варианты (массивы длиной 100 элементов) и получить значения для них.

9. Написать отчет и защитить у преподавателя.

2. Ход работы

1. Сортировка «Расческа»

Основная идея сортировки расческой заключается в устранении так называемых “черепах” – маленьких значений в конце массива, которые существенно замедляют сортировку пузырьком.

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

Оптимальное значение фактора уменьшения равно 1/(1-e^-φ) ≈ 1.247, где е – основание натурального логарифма, а φ – золотое сечение.

В процессе работы программы происходит последовательное создание и заполнение случайными числами 1000 массивов для каждой заданной длины. Далее происходит сортировка данных.

Помимо этого, фиксируется количество операций (перестановок и сравнений) в специально созданные переменные.

Полный код программы представлен в приложении А. Результат работы программы представлен на рисунке 2.1.1.

Рисунок 2.1.1 - Результат работы программы 1

В консольном выводе представляется размерность каждой тысячи массивов, среднее значение от суммы операций, а также среднее время выполнения сортировки.

Таблица 1 представляет собой таблицу со значениями длины массивов и средними значениями количества операций.

Таблица 1 - Средние значения количества операций сортировки «Расческа»

Размерность массивов	Среднее количество операций
1	1,000
2	3,494
3	7,131
4	12,054
5	17,950
10	56,224
15	97,351
20	160,066
25	221,440
30	269,370
50	585,504
75	958,216
100	1468,568
250	4701,664
500	10909,421

Далее необходимо построить график зависимости количества операций от длины массивов. График представлен на рисунке 2.1.2.

Рисунок 2.1.2 - График зависимости количества операций от длины массивов

Таблица 2 представляет собой таблицу со значениями длины массивов и среднего времени выполнения сортировки (среднего времени выполнения всех сравнений и перестановок).

Таблица 2 - Значения среднего времени выполнения операций сортировки

«Расческа»

Размерность массивов	Затраченное время (с)
1	0
2	0
3	0
4	0
5	0
10	0,000001
15	0,000001
20	0,000002
25	0,000002
30	0,000002
50	0,000005
75	0,000008
100	0,000016
250	0,000039
500	0,000081

Далее необходимо построить график зависимости затраченного на выполнение сортировки времени от длины массива. График представлен на рисунке 2.1.3.

Рисунок 2.1.3 - График зависимости затраченного времени от длины массивов

На основе полученных графиков, построим графики зависимостей y=n, y=n*log(n), y=n^2, y=n^3. Графики представлены на рисунке 2.1.4.

Рисунок 2.1.4 – Графики зависимости для сортировки «Расческа»

Проанализировав полученные результаты, можно сделать вывод о том, что график количества операций лежит между графиками y=n*log(n) и y=n^2. А следовательно, лучшее время для сортировки «Расческа» O(n*log(n)), а худшее - О(n^2).