СДлаб1
.pdf
Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Кафедра безопасности информационных систем (БИС)
Отчет по лабораторной работе №1 по дисциплине «Структуры данных»
Студент гр. 731-2
А.С. Батаев
подпись
дата
Преподаватель Д.Р. Уразаев
оценка подпись
дата
Томск 2022
Задание
Реализуйте сортировку расческой, быструю сортировку и еще одну по варианту. Продемонстрируйте на входных данных работоспособность вашего приложения и корректность реализации алгоритма сортировки. Реализуйте соответствующий варианту задания генератор входных данных.
Вариант 3. Третья сортировка - сортировка обменом. Входные данные представлены только отрицательными числами с плавающей точкой
(использовать float).
2
Содержание
1. |
Введение ......................................................................................................... |
4 |
|
2. |
Ход работы ..................................................................................................... |
5 |
|
|
2.1 |
Описание работы ..................................................................................... |
5 |
|
2.2 |
Блок-схема ................................................................................................... |
6 |
|
2.3 |
Скриншоты результатов программ ............................................................ |
8 |
Заключение ........................................................................................................... |
9 |
||
Приложение А .................................................................................................... |
10 |
||
Приложение Б..................................................................................................... |
11 |
||
Приложение В .................................................................................................... |
12 |
||
3
1.Введение
Целью данной работы является получение навыков работы с разными видами сортировки массивов на языке программирования C# в среде разработки Visual Studio 2022.
4
2.Ход работы
2.1Описание работы
Входе данной работе были реализованы три алгоритма сортировки.
Первый алгоритм сортировки – сортировка обменом или пузырьком.
Принцип работы пузырьковой сортировки состоит в том, что сравниваются попарно элементы массива, если элемент слева больше элемента справа, то элементы меняются местами, происходит это до тех пор пока массив не будет отсортирован.
Вторый – алгоритм быстрой сортировки. Быстрая сортировка является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две группы .
Третьий - алгоритм сортировки расческой. Сортировка расчѐской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком. Таким образом, мы упорядочиваем массив, постепенно распределяя значения в нѐм.
Сначала расстояние между элементами максимально, то есть равно размеру массива минус один. Затем, пройдя массив с этим шагом, необходимо поделить шаг на фактор уменьшения и пройти по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы.
5
Ниже в таблице 1 была приведена временная сложность этих алгоритмов, которая покажет их эффективность в работе с массивами.
Таблица 1 – Временная сложность алгоритмов
Алгоритм |
Структура |
|
Временная сложность |
Вспомогательные |
||||||||
|
данных |
|
|
|
|
|
|
|
|
данные |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Лучшее |
|
В худшем |
В худшем |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Расческа |
Массив |
|
O(n log(n)) |
|
|
O(n2) |
|
|
O(1) |
|
||
|
|
|
|
|
|
|
|
|||||
Быстрая |
Массив |
O(n log(n)) |
|
|
O(n |
2 |
) |
|
O(n) |
|
||
|
|
|
|
|
|
|
|
|
||||
Обменом |
Массив |
|
O(n) |
|
|
O(n |
2 |
) |
|
O(1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 1 – Сравнение алгоритмической сложности алгоритмов Исходя из сложностей алгоритма можно увидеть, что в худшем случае все три алгоритма работают одинаково. В лучшем случае минимальный
результат будет при использовании алгоритма расчески или быстрой сортировки.
2.2 Блок-схема
Для блок-схемы был выбран алгоритм сортировки обменом. Блок-
схема, представленная на рисунке 1, реализована с учѐтом задания.
В алгоритме реализовано заполнение массива только отрицательными числами с плавающей точкой от -999.999 до -0.001 .
6
Рисунок 2.1 – Блок-схема сортировки обменом
7
2.3 Скриншоты результатов программ
Результат работы программы сортировкой обменом представлен на рисунке 2.2. Листинг кода представлен в приложении А.
Рисунок 2.2 – Результат работы программы сортировкой обменом
Результат работы программы быстрой сортировкой представлен на
рисунке 2.3. Листинг кода представлен в приложении Б.
Рисунок 2.3 – Результат работы программы быстрой сортировкой
Результат работы программы сортировкой расческой представлен на рисунке 2.4. Листинг кода представлен в приложении В.
Рисунок 2.4 – Результат работы программы сортировкой расческой
8
Заключение
В результате выполнения данной лабораторной работы были разработаны алгоритмы сортировкой расческой, быстрой сортировки и сортировки обменом, в результате чего были получены навыки работы со структурами данных.
9
Приложение А
Сортировка обменом
Random rand = new Random(); int size = 10;
float[] array = new float[size]; float temp;
for (int i = 0; i < size; i++)
{
array[i] = rand.Next(-999999, -1) / 1000f;
Console.Write(array[i] + " ");
}
Console.WriteLine();
for (int i = 0; i < array.Length; i++)
{
for (int j = i + 1; j < array.Length; j++)
{
if (array[i] > array[j])
{
temp = array[i]; array[i] = array[j]; array[j] = temp;
}
}
}
for (int i = 0; i < 10; i++)
{
Console.Write(array[i] + " ");
}
10