Курсовая работа: Исследование методов сортировки

СОДЕРЖАНИЕ

1. ЦЕЛЬ И ПОСТАНОВКА ЗАДАЧИ.. 5

1.1. Цель работы.. 5

1.2. Задание. 5

2. ИСХОДНЫЕ ДАННЫЕ И ИНДИВИДУАЛЬНЫЙ ВАРИАНТ. 7

2.1. Индивидуальный вариант. 7

2.2. Формула определения размеров исследуемых массивов. 7

2.3. Вычисленные размеры массивов. 7

2.4. Модель вычислительного эксперимента. 8

3. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О МЕТОДАХ СОРТИРОВКИ.. 9

3.1. Пузырьковая сортировка. 9

3.2. Сортировка выбором. 9

3.3. Сортировка вставками. 10

3.4. Сортировка Шелла. 10

3.5. Быстрая сортировка. 10

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.. 12

4.1. Общая структура программного решения. 12

4.2. Критерий сортировки и представление данных. 12

4.3. Реализация алгоритмов сортировки. 12

4.4. Особенности экспериментальной версии программы.. 13

4.5. Формирование результатов эксперимента. 13

5. ДОКУМЕНТИРОВАНИЕ КОДА С ИСПОЛЬЗОВАНИЕМ DOXYGEN.. 14

5.1. Назначение и возможности системы Doxygen. 14

5.2. Главная страница документации. 14

5.3. Общая схема работы программы.. 15

5.4. Документирование функций программы.. 16

5.5. Документирование структур данных. 18

6. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНОГО ИССЛЕДОВАНИЯ.. 19

6.1. Таблица абсолютных значений. 19

6.2. Таблица нормированных значений. 19

6.3. Графики абсолютных значений. 22

6.4. Графики в логарифмической шкале. 23

6.5. Графики нормированных значений. 24

7. АНАЛИЗ РЕЗУЛЬТАТОВ.. 26

ЗАКЛЮЧЕНИЕ. 27

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 28

ПРИЛОЖЕНИЕ А.. 29

ПРИЛОЖЕНИЕ Б. 40

ВВЕДЕНИЕ

Сортировка данных является одной из ключевых задач в программировании и теории алгоритмов, поскольку от эффективности упорядочивания элементов во многом зависит производительность программных систем. При обработке больших объёмов информации выбор оптимального алгоритма сортировки может существенно повлиять как на скорость выполнения программы, так и на потребление вычислительных ресурсов.

В данной расчётно-графической работе проводится анализ пяти классических алгоритмов сортировки: пузырьковой сортировки, сортировки выбором, сортировки вставками, сортировки Шелла и быстрой сортировки. В соответствии с индивидуальным заданием (вариант 17) исследование проводится на задаче упорядочивания элементов каждого столбца целочисленной матрицы по убыванию. В рамках вычислительного эксперимента для каждого метода определяется количество сравнений и перестановок элементов при работе с массивами семи различных размеров, вычисляемых по формуле N = M², где M = 15·i·Number·Gruppa. Полученные результаты представлены в виде таблиц и графиков зависимости числа сравнений и перестановок от размера массива, в том числе с использованием логарифмической шкалы по основанию 3, что позволяет наглядно сравнить эффективность рассматриваемых алгоритмов.

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

Актуальность исследования обусловлена тем, что даже в учебных задачах выбор алгоритма сортировки оказывает значительное влияние на трудоёмкость вычислений, особенно при увеличении объёма данных. Применительно к задаче сортировки столбцов матрицы по убыванию данная зависимость проявляется особенно наглядно, поскольку общее число операций определяется суммой операций по каждому столбцу в отдельности. Понимание данной зависимости является важным навыком для разработчиков программного обеспечения.

1. ЦЕЛЬ И ПОСТАНОВКА ЗАДАЧИ

1. ЦЕЛЬ И ПОСТАНОВКА ЗАДАЧИ

1.1. Цель работы

Целью расчётно-графической работы является изучение методов сортировки данных и анализ зависимости характеристик их работы от размера исследуемого массива применительно к задаче упорядочивания столбцов целочисленной матрицы по возрастанию (вариант 10), а также изучение системы автоматического документирования программного кода Doxygen.

1.2. Задание

Выполнение работы осуществлялось на основе программы, созданной ранее в рамках лабораторной работы по теме «Методы сортировки». В соответствии с индивидуальным вариантом 10 объектом исследования является целочисленная матрица, каждый столбец которой подлежит независимой сортировке по возрастанию. Размеры исследуемых массивов вычисляются по формуле N = M², где M = k·i·Number Gruppa, i = 1..7. В ходе работы выполнялось исследование пяти методов сортировки и документирование программного кода.

В ходе выполнения работы были поставлены следующие задачи: создать документацию программного кода с использованием системы Doxygen с обязательным описанием назначения функций, их параметров и формируемых результатов обеспечить автоматическое построение схемы работы программы и графов вызовов функций провести экспериментальное исследование пяти методов сортировки — пузырьковой, выбором, вставками, Шелла и быстрой — на семи массивах различных размеров N1..N7 в соответствии с индивидуальным вариантом Реализовать сортировку каждого столбца матрицы по возрастанию и подсчитать для каждого метода суммарное число сравнений и перестановок элементов по всем столбцам Заполнить таблицу абсолютных значений исследуемых характеристик для каждого из семи размеров массива Провести нормирование числа сравнений и перестановок путём деления на соответствующий размер массива N и заполнить таблицу нормированных величин Построить графики абсолютных значений, графики в логарифмической шкале и графики нормированных характеристик в зависимости от размера массива Сделать вывод о качественных характеристиках исследованных методов сортировки и их применимости для обработки данных различного объёма.

Таким образом, постановка задачи включает в себя как практическую реализацию алгоритмов сортировки столбцов матрицы, так и последующий анализ результатов вычислительного эксперимента с использованием табличного и графического представления данных.

2. ИСХОДНЫЕ ДАННЫЕ И ИНДИВИДУАЛЬНЫЙ ВАРИАНТ

2.1. Индивидуальный вариант

В соответствии с методическими указаниями для выполнения расчётно-графической работы был выбран индивидуальный вариант №17. Номер академической группы принят равным 1. Согласно условиям варианта, при построении логарифмических графиков используется логарифм по основанию

2.2. Формула определения размеров исследуемых массивов

Для варианта №17 размер исследуемых массивов определяется через вспомогательную величину M(I), вычисляемую по формуле:

M(I) = k · I · Number · Gruppa, I = 1…7

Подставляя значения Number = 17, Gruppa = 1 и коэффициент k = 15, получаем:

M(I) = 15 · I · 17 · 1 = 255·I

Размер исследуемого массива определяется как квадрат данной величины:

N(I) = M(I)²

2.3. Вычисленные размеры массивов

На основании приведённых формул были рассчитаны значения M(I) и соответствующие размеры массивов N(I). Полученные данные использовались при проведении вычислительного эксперимента, а также при построении таблиц и графиков.

Следует отметить, что в экспериментальной реализации программы в качестве структуры данных использовалась квадратная матрица размерностью M(I)×M(I). При этом по оси абсцисс (X) в таблицах и графиках откладывалось значение N(I) = M(I)², соответствующее общему числу элементов матрицы.

Таблица 1. Значения M(I) и N(I) для варианта 10, группы 2