Файл: Сортировка данных в массиве. Оценка эффективности метода (Архитектура программы).pdf

2.2 Описание программных модулей

На рисунке 2.2 приведен компонентный состав модулей ПО ТМСМ в виде UML-диаграммы компонентов:

• ArraySorter.cs – модуль, включающий исполнение класса-сортировщика и реализацию всех рассматриваемых методов сортировки (см. п.2.2.1).
• ResPoint.cs – модуль класса представления точечного результата сортировки (см. п.2.2.1).
• MainSorterForm.cs – модуль пользовательского интерфейса ПО ТМСМ (см. п.2.2.1).
• .NET Framework 4.5 – пакет библиотек .NET, требуемых для функционирования приложения.

Рисунок 2.2 – Диаграмма компонентов ПО ТМСМ

Разработка основных функций сортировки данных

2.3 Разработка функции сортировки методом выбора

Сигнатура функции сортировки массива методом выбора приведена в листинге 2.1. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.1 – Сигнатура функции сортировки методом выбора

/// <summary>

/// Sort array by selections method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SelectionsSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом выбора приведен в приложении А.

На рисунке 2.3 приведена блок-схема алгоритма сортировки массива методом выбора. Эта и следующие блок-схемы в данной работе выполнены с помощью программы MS Visio 2016.

Рисунок 2.3 – Блок-схема алгоритма сортировки методом выбора

2.4 Разработка функции сортировки методом обмена

Сигнатура функции сортировки массива методом обмена приведена в листинге 2.2. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.2 – Сигнатура функции сортировки методом обмена

/// <summary>

/// Sort array by bubbles method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] BubbleSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом обмена приведен в приложении Б.

На рисунке 2.4 приведена блок-схема алгоритма сортировки массива методом обмена.

Рисунок 2.4 – Блок-схема алгоритма сортировки методом обмена

2.5 Разработка функции сортировки методом вставок

Сигнатура функции сортировки массива методом вставок приведена в листинге 2.3. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.3 – Сигнатура функции сортировки методом вставок

/// <summary>

/// Sort array by insertions method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] InsertionsSort<T>(T[] __array_) where T : IComparable<T>

Полный листинг функции сортировки массива методом вставок приведен в приложении В.

На рисунке 2.5 приведена блок-схема алгоритма сортировки массива методом вставок.

Рисунок 2.5 – Блок-схема алгоритма сортировки методом вставок

2.6 Разработка функции сортировки методом Шелла

Сигнатура функции сортировки массива методом Шелла приведена в листинге 2.4. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.4 – Сигнатура функции сортировки методом Шелла

/// <summary>

/// Sort array by Shell method

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] SortByShell<T>(T[] __array_) where T: IComparable<T>

Полный листинг функции сортировки массива методом Шелла приведен в приложении Г.

На рисунке 2.6 приведена блок-схема алгоритма сортировки массива методом Шелла.

Рисунок 2.6 – Блок-схема алгоритма сортировки методом Шелла

2.7 Разработка функции метода быстрой сортировки

Сигнатура функции метода быстрой сортировки массива приведена в листинге 2.5. Функция принимает исходный массив __array_ в качестве аргумента и возвращает уже отсортированный массив.

Листинг 2.5 – Сигнатура функции сортировки методом выбора

/// <summary>

/// Sort array by quick sort

/// </summary>

/// <param name="__array_">Array to sort</param>

/// <returns>Array after sorting</returns>

/// <typeparam name="T">any type of array elements</typeparam>

public static T[] QuickSort<T>(T[] __array_) where T : IComparable<T>

Метод быстрой сортировки использует рекурсивную процедуру – _quickSort сортировки подмассивов (левого и правого относительно выбранного опорного элемента). Функция __quickSort принимает исходный массив на текущей итерации сортировки и индексы левого и правого подмассивов. Общая сигнатура данной рекурсивной функции приведена в листинге 2.6.

Листинг 2.6 – Сигнатуры функций сортировки методом выбора

/// <summary>

/// Recurrent quick sort

/// </summary>

/// <typeparam name="T">any type of array elements</typeparam>

/// <param name="__array_">Part of array to sort on current step</param>

/// <param name="left"></param>

/// <param name="right"></param>

private static void _quickSort<T>(T[] __array_, int left, int right) where T : IComparable<T>

Полный листинг функции алгоритма метода быстрой сортировки приведен в приложении Д.

На рисунке 2.7 приведена блок-схема алгоритма метода быстрой сортировки массива – главной функции QuickSort и функции рекурсивной сортировки __quickSort.

Рисунок 2.7 – Блок-схема алгоритма методом быстрой сортировки

Описание интерфейса программы

Интерфейс ПО ТМСТ состоит из одного главного окна, на котором расположены (рисунок 2.8):

• область выбора тестируемых методов сортировки;
• область настройки параметров эксперимента типа 1 (исследование эффективности методов сортировки в зависимости от размера массива);
• область настройки параметров эксперимента типа 2 (исследование эффективности методов сортировки в зависимости от исходной степени упорядоченности массива);
• область вывода результатов эксперимента типа 1 в виде графических зависимостей;
• область вывода результатов эксперимента типа 2 в виде графических зависимостей;

Рисунок 2.8 – Вид главного окна ПО ТМСМ

Вывод по главе 2

В ходе работы было разработано математическое и программное обеспечение, которое способно воспроизводить два типа экспериментов с целью исследования эффективности сортировки массивов данных:

• эксперимент типа 1, в котором будет определена зависимость количества произведенных операций и фактически затраченного времени от размера исходного массива (исходная степень упорядоченности массива будет задаваться постоянной в ходе всего эксперимента);
• эксперимент типа 2, в котором будет определена зависимость количества произведенных операций и фактически затраченного времени от исходной степени упорядоченности массива (размер массива будет задаваться постоянной в ходе всего эксперимента).

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

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

• с изменением размера сортируемой последовательности для различных степеней исходной упорядоченности;
• с изменением степени исходной упорядоченности сортируемой последовательности для различного размера.

В ходе экспериментов будут определяться и строиться графики следующих параметров:

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

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

• генерирование абсолютно упорядоченной последовательности;
• замена заданного процента элементов последовательности случайными числами в случайных местах.

3. Проведение экспериментов по сортировке последовательности с изменением ее длины разными методами

Эксперимент с изменением размера сортируемой последовательности будет проводиться для диапазона значений длины массива от 1000 до 10000 элементов. Будет проведена серия из трех таких экспериментов для различных степеней исходной упорядоченности: 0% (абсолютно упорядоченный массив), 50% (частично упорядоченный массив), 100% (абсолютно неупорядоченный массив).

На рисунке 3.1 приведены результаты зависимости характеристик сортировки от размера абсолютно упорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.1 – Результаты эксперимента сортировки абсолютно упорядоченного массива с изменением размера от 1000 до 10000 элементов

На рисунке 3.2 приведены результаты зависимости характеристик сортировки от размера частично упорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.2 – Результаты эксперимента сортировки частично упорядоченного массива с изменением размера от 1000 до 10000 элементов

На рисунке 3.3 приведены результаты зависимости характеристик сортировки от размера абсолютно неупорядоченного массива в диапазоне от 1000 до 1000 элементов.

Рисунок 3.3 – Результаты эксперимента сортировки абсолютно неупорядоченного массива с изменением размера от 1000 до 10000 элементов

Проведение экспериментов по сортировке последовательности с изменением степени ее исходной упорядоченности разными методами

Эксперимент с изменением степени исходной упорядоченности сортируемой последовательности будет проводиться для диапазона от 0 (абсолютно упорядоченный) до 100 (абсолютно неупорядоченный) процентов. Будет проведено два таких экспериментов для различных размеров: 1000 и 10000 элементов.

На рисунке 3.4 приведены результаты эксперимента сортировки массива из 1000 элементов с изменением степени исходной упорядоченности от 0 до 100 процентов.

Рисунок 3.4 – Результаты эксперимента сортировки массива из 1000 элементов с изменением степени исходной упорядоченности от 0% до 100%

На рисунке 3.5 приведены результаты эксперимента сортировки массива из 10000 элементов с изменением степени исходной упорядоченности от 0 до 100 процентов.

Рисунок 3.5 – Результаты эксперимента сортировки массива из 10000 элементов с изменением степени исходной упорядоченности от 0% до 100%

Вывод по главе 3

Результаты проведенных экспериментов (3.1 – 3.5) показали, что:

• в общем случае самым неэффективным методом является сортировка обменом (достаточно одного элемента, перемещаемого из начала в конец, что уже дает существенный прирост к числу операций и, соответственно, времени);
• более эффективными в общем случае являются сортировки выбором и вставками, причем сортировка вставками работает немного быстрее;
• сортировка Шелла и быстрая сортировка теряет эффективность при хорошей степени упорядоченности исходной последовательности, в то время как, например, сортировка обменом, наоборот, продемонстрировала высокую скорости работы;
• тем не менее, в общем случае (а при реальном применении таких случаев подавляющее большинство) наибольшей эффективностью по всем параметрам являются быстрая сортировка и сортировка Шелла.