Алгоритмы сортировки

Бюджетное учреждение высшего образования

Ханты-Мансийского автономного округа

«Сургутский государственный университет»

Политехнический институт

Кафедра автоматики и компьютерных систем

Отчет

по лабораторной работе № 2

по дисциплине «Структуры и алгоритмы обработки данных»

Тема: “Алгоритмы сортировки”

Выполнил: студент группы 609-91

Джетписов К.С.

Проверил: преподаватель кафедры АиКС

Назаров Е В.

Сургут

2023 г.

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

Задание:

•  В таблице № 1 представлены алгоритмы сортировки (и в некоторых случаях их параметры), которые необходимо реализовать в соответствии с вариантом (таблица № 2). Для проверки реализованных функций сортировки разработать функцию, проверяющую упорядоченность элементов в последовательности.
• Разработать функции, позволяющие производить оценку временной сложности алгоритма T(n) (n – количество элементов сортируемой последовательности) и суммарного количества операций сравнения S(n)1, выполняемых в ходе его работы.
• На основе функций формирования последовательностей, реализованных в ходе предыдущей лабораторной работы, и результатов выполнения пп. 1 и 2, разработать программу, с помощью которой по экспериментальным данным построить зависимости T(n) и S(n) для заданных алгоритмов сортировки по четырем последовательностям (упорядоченная, случайная, упорядоченная в обратном порядке и указанная в варианте). Размеры сортируемых последовательностей следует выбирать самостоятельно в соответствии с характеристиками исследуемого алгоритма. Кроме того, необходимо оценить зависимости T(n) и S(n) для функции qsort из стандартной библиотеки C.

Ход Работы:
Вариант 5

3 Модифицированный метод «пузырька» II

4 Двунаправленный метод обмена

15 Сортировка Шелла

Зависимость времени сортировки от количества символов в последовательности.

Для ниже изображенных графиков актуально следующее распределите цветов:

Серый - используется для упорядоченной последовательности.

Желтый - для обратно упорядоченной.

Синий - случайная последовательность.

Оранжевый - пилообразная.

Эти типы последовательностей были поданы на вход алгоритма сортировки.

[pic 1]

График 1. Сортировка пузырьком c использованием индекса последнего обмена.