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

МИНОБРНАУКИ РОССИИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕУЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»Институт прикладной математики и компьютерных наукАлгоритмы устойчивой сортировки: сортировка вставками и пузырьком (гибрид). Графы: представление. (тема курсовой работы)ПОЯСНИТЕЛЬНАЯ ЗАПИСКАк курсовой работепо дисциплине_____________________________________________________________(полное наименование учебной дисциплины)

Студент гр.	______________	______________	______________
	(индекс группы)	(подпись и дата)	(инициалы и фамилия)

Руководитель	______________	______________	______________
	(должность и ученая степень)	(подпись и дата)	(инициалы и фамилия)

ТУЛА 2023

УТВЕРЖДАЮ

Директор ИПМКН

___________А.А.Сычугов

"___"___________20__г.

ЗАДАНИЕна курсовую работу по программированиюстудента гр. __________________________________________________ТЕМА: ___________________________________________________________________________________________________________________Исходные данные _______________________________________________________________________________________________________________________________________________________________________Задание получил:______________________________________________Дата выдачи задания :__________________________________________Задание выдал:________________________________________________Срок защиты курсовой работы: __________________________________Замечания консультанта: _________________________________________________________________________________________________________________________________________________________________К защите допущен. Консультант работы __________________________

"___"______________20__г.

Введение 4

Глава 1. Алгоритмы устойчивой сортировки: сортировка вставками и пузырьком (гибрид) 5

1. Постановка задачи 5

2. Описание входной и выходной информации 5

3. Алгоритм решения задачи 6

4. Общие требования к программе 11

5. Описание структуры программы для решения задачи 11

6. Инструкции по эксплуатации программ 12

7. Описание контрольного примера 14

Глава 2. Графы: представление 18

1. Постановка задачи 18

2. Описание входной и выходной информации 19

3. Алгоритм решения задачи 20

4. Общие требования к программе 22

5. Описание структуры программы для решения задачи 23

6. Инструкции по эксплуатации программ 26

7. Описание контрольного примера 27

Заключение 30

Список литературы 31

Приложение 1 32

Приложение 2 34

Введение

В данной курсовой работе рассматривается разработка программ, реализующих алгоритмы устойчивой сортировки (сортировка вставками и сортировка пузырьком) и представление графов на языке программирования C++. Алгоритмы сортировки являются важной частью компьютерных наук и широко применяются в различных областях. Сортировка вставками и сортировка пузырьком относятся к простым и понятным алгоритмам, которые хорошо подходят для обучения и понимания основных принципов сортировки. Сортировка вставками основана на принципе вставки элемента в уже отсортированную последовательность. Этот алгоритм хорошо работает на небольших массивах и обладает устойчивостью, то есть сохраняет относительный порядок элементов с одинаковыми значениями. Сортировка пузырьком, в свою очередь, сравнивает и меняет местами соседние элементы до тех пор, пока массив не будет полностью отсортирован. Хотя этот алгоритм не является эффективным для больших массивов, он также является устойчивым и простым в реализации. Вторая часть курсовой работы посвящена представлению графов. Графы являются важной структурой данных и используются для моделирования связей между объектами в различных областях, таких как социальные сети, транспортные сети, и информационные системы. Представление графов позволяет эффективно работать с ними и решать разнообразные задачи, включая поиск кратчайшего пути, обход графа, и выявление связей между узлами.Для реализации алгоритмов сортировки и представления графов будет использован язык программирования C++, который широко применяется для разработки эффективных и надежных программ. Работа будет включать описание алгоритмов, приведение их псевдокода, и реализацию программ с использованием языка C++. В заключении будут проанализированы результаты работы программ и обсуждены их преимущества и недостатки.

Цель данной курсовой работы состоит в том, чтобы изучить алгоритмы устойчивой сортировки и представления графов, а также научиться применять их в практических задачах на языке программирования C++.

Глава 1. Алгоритмы устойчивой сортировки: сортировка вставками и пузырьком (гибрид)

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

Данная программа должна реализовать гибридный алгоритм сортировки (сортировку вставками и пузырьком) на трех типах данных: целочисленных числах, вещественных числах и строках. Программа должна генерировать случайные данные каждого типа, сохранять их в отдельных файлах, затем сортировать данные с помощью гибридного алгоритма сортировки и измерять время, затраченное на сортировку для каждого типа данных. Отсортированные данные должны сохраняться в отдельных файлах.Основной целью программы является демонстрация работы гибридного алгоритма сортировки на различных типах данных и сравнение времени, затраченного на сортировку каждого типа. Программа также должна предоставлять возможность сохранения исходных и отсортированных данных в файлах для дальнейшего анализа или использования.Программа должна использовать библиотеки стандартного C++ для работы с контейнерами, случайной генерацией данных, измерения времени и файловым вводом-выводом.

2. Описание входной и выходной информации

Входная информация:- Размер данных (dataSize): определяет количество элементов, которые будут сгенерированы и отсортированы для каждого типа данных (целочисленные числа, вещественные числа, строки).- Нетребуется пользовательского ввода.Выходная информация:- Консольный вывод: программа выводит информацию о времени, затраченном на сортировку каждого типа данных. Выводятся три значения времени: время, затраченное на сортировку целочисленных чисел, время на сортировку вещественных чисел и время на сортировку строк.- Файлы сгенерированных данных: программа сохраняет исходные случайно сгенерированные данные каждого типа (целочисленные числа, вещественные числа, строки) в отдельных файлах: "integer_source.txt", "real_source.txt" и "string_source.txt".- Файлы отсортированных данных: программа сохраняет отсортированные данные каждого типа (целочисленные числа, вещественные числа, строки) в отдельных файлах: "integer_sorted.txt", "real_sorted.txt" и "string_sorted.txt".Программа не предусматривает пользовательского ввода данных или выбора способа сортировки. Она автоматически генерирует случайные данные, сортирует их с использованием гибридного алгоритма сортировки вставками и пузырьком, и выводит информацию о затраченном времени на сортировку каждого типа данных. Пользователь может использовать сгенерированные файлы с данными для своих целей, таких как анализ производительности или дальнейшая обработка.

3. Алгоритм решения задачи

Алгоритм сортировки вставками:1. Перебираем элементы массива, начиная со второго элемента (индекс 1).2. Сравниваем текущий элемент со всеми предыдущими элементами, начиная с предыдущего элемента (индекс j) до первого элемента (индекс 0).3. Если текущий элемент меньше предыдущего, меняем их местами.4. Повторяем шаги 2-3, пока не достигнем начала массива или не найдем место для вставки текущего элемента.5. Переходим к следующему элементу и повторяем шаги 2-4 для всех оставшихся элементов.6. После завершения цикла перебора элементов, массив будет отсортирован по возрастанию.Алгоритм сортировки пузырьком:1. Перебираем элементы массива с индексом i от 0 до n-1, где n - размер массива.2. Для каждого i сравниваем текущий элемент с его соседним элементом (i и i+1).3. Если текущий элемент больше следующего, меняем их местами.4. Повторяем шаги 2-3 для всех элементов массива, начиная с индекса 0 и до n-1-i.5. После завершения внешнего цикла сортировки (цикл по i), самый большой элемент будет перемещен в конец массива.6. Повторяем шаги 1-5 для n-1 раз, где n - размер массива, чтобы полностью отсортировать массив.Гибридный алгоритм сортировки вставками и пузырьком:1. Инициализируем переменные: размер массива (n), зазор (gap) равный n, флаг swapped для отслеживания перестановок.2. Пока зазор больше 1 или были выполнены перестановки:- Если зазор больше 1, уменьшаем его на фиксированный фактор уменьшения (например, gap = (gap * 10) / 13) и проверяем, не стал ли зазор меньше 1. Если да, устанавливаем зазор равным 1.- Устанавливаем флаг swapped в значение false.- Перебираем элементы массива с индексом i от 0 до n-gap.- Если элемент с индексом i больше элемента с индексом i+gap, меняем их местами и устанавливаем флаг swapped в значение true.- Если зазор равен 1, выполняем вставочную/пузырьковую сортировку для последнего прохода:- Перебираем элементы массива с индексом i от 0 до n-1.- Инициализируем флаг sorted в значение true.- Перебираем элементы массива с индексом j от 0 до n-i-1.- Если элемент с индексом j больше элемента с индексом j+1, меняем их местами и устанавливаем флаг sorted в значение false.- Если флаг sorted равен true, прерываем внутренний цикл.3. После завершения внешнего цикла сортировки, массив будет отсортирован по возрастанию.Гибридный алгоритм комбинирует преимущества сортировки вставками (эффективность при частично упорядоченных данных) и сортировки пузырьком (способность обнаруживать и перемещать наибольшие элементы). Первоначально используется сортировка вставками с изменяемым зазором, который постепенно уменьшается. Затем, для последнего прохода, применяется сортировка пузырьком, чтобы окончательно упорядочить оставшиеся элементы. Это позволяет гибридному алгоритму достичь хорошей производительности в широком диапазоне случаев сортировки данных.

Рисунок 1 - Блок-схема алгоритма сортировкиРисунок 2 - Блок-схема алгоритма сортировки

4. Общие требования к программе

Требования к программе:- Программа должна быть написана на языке C++.- Программа должна использовать стандартные библиотеки C++ для работы с векторами, случайными числами, файлами и измерения времени выполнения.- Программа должна предоставлять функцию `hybridSort`, реализующую гибридный алгоритм сортировки вставками и пузырьком.- Программа должна генерировать случайные данные для каждого типа: целочисленные, вещественные числа и строки.- Программа должна сохранять исходные и отсортированные данные в отдельных файлах.- Программа должна выводить в консоль время, затраченное на сортировку каждого типа данных.

5. Описание структуры программы для решения задачи

Программа характеризуется следующей структурой:Определение функции `hybridSort`, которая реализует гибридный алгоритм сортировки вставками и пузырьком.Функция `main`, которая является точкой входа в программу:- Инициализация переменных, включая размер данных (`dataSize`).- Создание векторов для хранения целых чисел (`integerData`), вещественных чисел (`realData`) и строк (`stringData`).- Генерация случайных данных для каждого типа и сохранение исходных данных в отдельных файлах (`integer_source.txt`, `real_source.txt`, `string_source.txt`).- Сортировка каждого вектора с использованием гибридного алгоритма и измерение времени, затраченного на сортировку.- Вывод времени сортировки для каждого типа данных.- Сохранение отсортированных данных в отдельных файлах (`integer_sorted.txt`, `real_sorted.txt`, `string_sorted.txt`).- Завершение программы.Вывод результатов и времени выполнения процесса.Структура программы обеспечивает генерацию случайных данных, их сортировку с использованием гибридного алгоритма и сохранение исходных и отсортированных данных в файлах. Также она измеряет время, затраченное на сортировку каждого типа данных, и выводит его в консоль.

6. Инструкции по эксплуатации программ

Инструкция по эксплуатации программы может выглядеть следующим образом:1. Установка и запуск программы:- Убедитесь, что на вашем компьютере установлена среда разработки C++ (например, Visual Studio) или компилятор C++ (например, GCC).