Файл: Лабораторная работа дисциплина (модуль) Алгоритмы и структуры данных.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 22
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)
ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
В Г. ТАГАНРОГЕ РОСТОВСКОЙ ОБЛАСТИ
ПИ (филиал) ДГТУ в г. Таганроге
Факультет «ВО___________________________________»
наименование факультета
Кафедра «Автомобилестроение и сервис транспортных средств»
наименование кафедры
ЛАБОРАТОРНАЯ РАБОТА
Дисциплина (модуль) Алгоритмы и структуры данных ________________________
(наименование учебной дисциплины (модуля))
Направление подготовки/специальность _09.03.01 Информатика и вычислительная техника__
код наименование направление/специальности
Обозначение работы Лабораторная работа «Простые сортировки на месте»__________________
Номер зачетной книжки _2165298___ Номер варианта __________ Группа ВО ИВТ-2221_______
Обучающийся ___________________ В.В. Конгар._____________________________________
подпись, дата И.О. Фамилия
Контрольную работу проверил ________ ___________
подпись, дата должность, И.О. Фамилия
г. Таганрог
2022 г.
Цель работы: ознакомиться и реализовать простые методы сортировки — сортировки обменом, выбором, вставками, бинарными вставками. Исследовать сложность указанных алгоритмов сортировки.
Ход работы
1.Пишем код на С++
Пузырьковая сортировка
Результат
Сортировка прямым выбором
Результат
Сортировка прямыми включениями/вставками
Результат
2. Найти среднее количество сравнений и перестановок, выполняемых программой для сортировки массивов из 100, 200, 300, 500, …, 10000 элементов.При сортировке пузырьком максимальное число сравнений составляет 0,5N², а среднее число сравнений приблизительно 0,25N². N-длина массива.
Число перестановок равно 0,75 N².
Я рассчитывал значения в Excel, для удобства.
При сортировке выбором число сравнений прежнее, а число перестановок будет приблизительно равно N*(ln N + g), где g- константа Эйлера=0,577216
Число сравнений при сортировке вставками рассчитывается по формуле
(N²+N-2)/4 , а число перестановок по формуле (N²+9N-10)/4
3.По полученным данным составим график зависимости сложности сортировки от размеров массива.
Вывод: в ходе работы мы познакомились с тремя основными методами сортировки массивов. Из полученных сведений я могу сделать вывод, что метод сортировки «пузырьком» самый неэффективный из представленных.
Могу сделать вывод, что при работе с относительно маленькими массивами лучше использовать метод сортировки «выбором», так как у него наименьшее кол-во перестановок. Однако метод сортировки «вставками» обгоняет его при работе с большими массивами, потому что у него меньше число сравнений.