Файл: Лабораторная работа дисциплина (модуль) Алгоритмы и структуры данных.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 97
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»В Г. ТАГАНРОГЕ РОСТОВСКОЙ ОБЛАСТИПИ (филиал) ДГТУ в г. ТаганрогеФакультет «ВО___________________________________»наименование факультета Кафедра «Автомобилестроение и сервис транспортных средств»наименование кафедры ЛАБОРАТОРНАЯ РАБОТАДисциплина (модуль) Алгоритмы и структуры данных ________________________(наименование учебной дисциплины (модуля)) Направление подготовки/специальность _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)/43.По полученным данным составим график зависимости сложности сортировки от размеров массива.Вывод: в ходе работы мы познакомились с тремя основными методами сортировки массивов. Из полученных сведений я могу сделать вывод, что метод сортировки «пузырьком» самый неэффективный из представленных.
Сортировка прямым выборомРезультат Сортировка прямыми включениями/вставкамиРезультат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)/43.По полученным данным составим график зависимости сложности сортировки от размеров массива.Вывод: в ходе работы мы познакомились с тремя основными методами сортировки массивов. Из полученных сведений я могу сделать вывод, что метод сортировки «пузырьком» самый неэффективный из представленных.
Могу сделать вывод, что при работе с относительно маленькими массивами лучше использовать метод сортировки «выбором», так как у него наименьшее кол-во перестановок. Однако метод сортировки «вставками» обгоняет его при работе с большими массивами, потому что у него меньше число сравнений.