СДлб2
.pdf
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ Отчет по практической работе №2
по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
Принял:
преподаватель КИБЭВС Д.Р. Уразаев
Томск 2022
|
|
|
СОДЕРЖАНИЕ |
1 |
Введение................................................................................................................................. |
3 |
|
2 |
Ход работы ............................................................................................................................. |
4 |
|
|
2.1 |
Быстрая сортировка......................................................................................................... |
4 |
|
2.2 |
Сортировка расческой..................................................................................................... |
6 |
|
2.3 |
Cортировка обменом....................................................................................................... |
8 |
3 Худший и лучший случай........................................................................................................ |
11 |
||
Заключение ................................................................................................................................. |
13 |
||
Приложение А............................................................................................................................. |
14 |
||
Приложение Б ............................................................................................................................. |
16 |
||
Приложение В ............................................................................................................................. |
17 |
||
2
1 Введение
Целью работы является овладеть навыками работы с простыми структурами данных на примере массивов, а также их сортировки тремя методами. В качестве ТЗ мне было выдано следующее задание: Последовательно задайте длину массивов 1, 2, 3, 4, 5, 10, 15, 20,25, 30, 40,50, 75, 100,150,200,250,
300, 400, 500, 600, 800, 1000. Отсортировать все массивы при помощи ранее реализованных алгоритмов сортировки и подсчитать количество операций,
выполненных для их сортировки (количество сравнений + количество перестановок) и время, затраченное на сортировку массивов. Вывести на графики данные по числу операций, по времени сортировки в зависимости от размера массива (зависимость числа операций от размера массива, зависимость времени выполнения алгоритма от размера массива). Для каждой сортировки сделать разные графики.
3
2 Ход работы
2.1 Быстрая сортировка
На рисунке 2.1 представлен результат работы программы по вычислению алгоритмической сложности алгоритма быстрой сортировки.
Рисунок 2.1 – Временная сложность по вычислению алгоритмической сложности сортировки расческой
В приложении А представлен листинг быстрой сортировки.
На рисунках представлены графики зависимости количество тактов
(Рисунок 2.2) и количества операций (Рисунок 2.3) от размерности массива.
4
Рисунок 2.2-Графики зависимости тактов
5
Рисунок 2.2-Графики зависимости количества операций Из графического отображения полученных данных можно увидеть, что
график лежит между эталонными, что подтверждает теорию.
В приложении А представлен листинг программы сортировки вставками.
2.1 Сортировка расческой
На рисунке 2.4 представлен результат работы программы по сортировке расческой.
6
Рисунок 2.4 – Сортировка расческой
В приложении Б представлен листинг программы сортировки расческой.
На рисунках представлены графики зависимости количество тактов
(Рисунок 2.5) и количества операций (Рисунок 2.6) от размерности массива
Рисунок 2.5-Графики зависимости тактов
7
Рисунок 2.6 - Графики зависимости количества операций Из графического отображения полученных данных можно увидеть, что
график лежит между эталонными, что подтверждает теорию.
В приложении Б представлен листинг программы сортировки вставками.
2.2 Сортировка обменом
На рисунке 2.7 представлен результат работы программы по сортировке обменом.
8
Рисунок 2.7 - Сортировка обменом
Рисунок 2.8-Графики зависимости тактов
9
Рисунок 2.9 - Графики зависимости количества операций Из графического отображения полученных данных можно увидеть, что
график лежит между эталонными, что подтверждает теорию.
В приложении В представлен листинг программы сортировки обменом.
10