Исследование алгоритмов сортировки в среде ОС Windows. Гераськов_ТСЗ201-Бк18_курсовая. Курсовая работа по дисциплине Алгоритмические языки и программирование Исследование алгоритмов сортировки в среде ос
 Скачать 64.36 Kb.
|
 МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский авиационный институт (национальный исследовательский университет)» Ступинский филиал МАИ Кафедра «Моделирование систем и информационные технологии» КУРСОВАЯ РАБОТА по дисциплине «Алгоритмические языки и программирование» Исследование алгоритмов сортировки в среде ОС Windows
Москва 2020 МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФ Федеральное государственное бюджетное образовательное учреждение высшего образования «Московский авиационный институт (национальный исследовательский университет)» Ступинский филиал МАИ Кафедра «Моделирование систем и информационные технологии» УТВЕРЖДАЮ Заведующий кафедрой МСиИТ _______________ И. М. Мамонов (И.О.Фамилия) « 19 » февраля 2020 г. З А Д А Н И Е на курсовой проект по дисциплине«Алгоритмические языки и программирование» Студент ТСЗ-201Бк-18,_Гераськов Д.А__________________ (№ группы, Ф. И. О.) Тема Исследование алгоритмов сортировки в среде ОС Windows Перечень вопросов, подлежащих разработке в курсовой работе Выполнить краткую характеристику исследуемых алгоритмов сортировки. Разработать и привести листинг исследовательской программы. Выполнить описание исследовательской программы (описание назначения и параметров подпрограмм, описание назначения глобальных переменных, блок-схема программы). Построить таблицу и график результатов исследования. Провести анализ результатов эксперимента и сделать выводы. Рекомендуемая литература 1) Джон Шарп: Microsoft Visual C#. Подробное руководство — Питер, 2017 г. — 848 c. 2) Джон Скит: C# для профессионалов. Тонкости программирования 3-е издание — Вильямс, 2017 г. — 608 с. 3) Албахари Джозеф, Албахари Бен: C# 8.0. Карманный справочник — Диалектика, 2020 г. — 240 с. 4) Мартин Роберт, Мартин Мика Принципы, паттерны и методики гибкой разработки на языке C# — Символ-Плюс 2011 г. — 768 с. 5) Raihan Taher: Hands-On Object-Oriented Programming with C# — Packt Publishing 2019 г. — 288 c. 6) Прайс Марк: C# 7 и .NET Core. Кросс-платформенная разработка для профессионалов — Питер, 2018 г. — 640 c. Задание выдано «19» февраля 2020 г. Руководитель Б. Б. Новиков, ассистент (Ф. И. О., должность, подпись) Студент (подпись) ВВЕДЕНИЕ Алгоритмы сортировки используются в практически любой программной системе. Целью алгоритмов сортировки является упорядочение последовательности элементов данных. Поиск элемента в последовательности отсортированных данных занимает время, пропорциональное логарифму количества элементов в последовательности, а поиск элемента в последовательности неотсортированных данных занимает время, пропорциональное количеству элементов в последовательности, т.е. намного большее. Кроме того, отсортированные данные эстетически предпочтительнее неотсортированных. Существует множество различных методов сортировки данных. Однако любой алгоритм сортировки можно разбить на три основные части: Cравнение, определяющее упорядоченность пары элементов; Перестановку, меняющую местами пару элементов; Собственно, сортирующий алгоритм, который осуществляет сравнение и перестановку элементов данных до тех пор, пока все эти элементы не будут упорядочены. Важнейшей характеристикой любого алгоритма сортировки является скорость его работы, которая определяется функциональной зависимостью среднего времени сортировки последовательностей элементов данных, заданной длины, от этой длины. Время сортировки будет пропорционально количеству сравнений и перестановок элементов данных в процессе их сортировки. Цель исследования Цели курсовой работы: изучить временные характеристики алгоритмов сортировки данных, приобрести навыки работы в среде ОС Windows. Характеристика исследуемых алгоритмов сортировки Метод пузырька Идея данной сортировки заключается в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются {\displaystyle N-1}N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма). Создаём метод BubbleSort. В него будет передан массив mas, который мы заполним числами для сортировки. Здесь мы сравниваем, так сказать, предыдущий элемент (i) с последующим (j).Если элемент массива под номером i будет больше, чем элемент массива под номером j, то меняем элементы местами и продолжаем сравнение дальше static int[] BubbleSort(int[] mas) { int temp; for (int i = 0; i < mas.Length; i++) { for (int j = i + 1; j < mas.Length; j++) { if (mas[i] > mas[j]) { temp = mas[i]; mas[i] = mas[j]; mas[j] = temp; } } } return mas; } Быстрая сортировка (quick sort), или сортировка Хоара – один из самых быстрых алгоритмов сортирования данных. Алгоритм Хоара – это модифицированный вариант метода прямого обмена. Другие популярные варианты этого метода - сортировка пузырьком и шейкерная сортировка, в отличии от быстрой сортировки, не очень эффективны. Идея алгоритма следующая: Необходимо выбрать опорный элемент массива, им может быть любой элемент, от этого не зависит правильность работы алгоритма; Разделить массив на три части, в первую должны войти элементы меньше опорного, во вторую - равные опорному и в третью - все элементы больше опорного; Рекурсивно выполняются предыдущие шаги, для подмассивов с меньшими и большими значениями, до тех пор, пока в них содержится больше одного элемента. Поскольку метод быстрой сортировки разделяет массив на части, он относиться к группе алгоритмов разделяй и властвуй. Достоинства: Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения. Алгоритм очень короткий: запомнив основные моменты, его легко написать «из головы», невелика константа при {\displaystyle n\log n} n log n. Требует лишь{\displaystyle O(\log n)} O(log n) дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае {\displaystyle O(n)}O(n) памяти) Хорошо сочетается с механизмами кэширования и виртуальной памяти. Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах). Допускает эффективную модификацию для сортировки по нескольким ключам (в частности — алгоритм Седжвика для сортировки строк): благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу. Работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу. Недостатки: Сильно деградирует по скорости (до {\displaystyle O(n^{2})} O(n^2)) в худшем или близком к нему случае, что может случиться при неудачных входных данных. Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать {\displaystyle O(n)}O(n) вложенных рекурсивных вызовов. Неустойчив. //метод возвращающий индекс опорного элемента static int Partition(int[] array, int minIndex, int maxIndex) { int pivot = minIndex - 1; for (int i = minIndex; i < maxIndex; i++) { if (array[i] < array[maxIndex]) { pivot++; Swap(ref array[pivot], ref array[i]); } } pivot++; Swap(ref array[pivot], ref array[maxIndex]); return pivot; } //быстрая сортировка static int[] QuickSort(int[] array, int minIndex, int maxIndex) { if (minIndex >= maxIndex) { return array; } int pivotIndex = Partition(array, minIndex, maxIndex); QuickSort(array, minIndex, pivotIndex - 1); QuickSort(array, pivotIndex + 1, maxIndex); return array; } //Перегруженный метод static int[] QuickSort(int[] array) { return QuickSort(array, 0, array.Length - 1); } Сортировка с помощью двоичного дерева Универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли). Эффективность Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка {\displaystyle O(log(n))}O(log(n)). Соответственно, для n объектов сложность будет составлять {\displaystyle O(n\,log(n))}O(Log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать {\displaystyle O(n)}O(n), что может привести к общей сложности порядка {\displaystyle O(n^{2})}O(n^2). При физическом развёртывании древовидной структуры в памяти требуется не менее чем {\displaystyle 4n}4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память. public class TreeNode { public TreeNode(int data) { Data = data; } //данные public int Data { get; set; } //левая ветка дерева public TreeNode Left { get; set; } //правая ветка дерева public TreeNode Right { get; set; } //рекурсивное добавление узла в дерево public void Insert(TreeNode node) { if (node.Data < Data) { if (Left == null) { Left = node; } else { Left.Insert(node); } } else { if (Right == null) { Right = node; } else { Right.Insert(node); } } } //преобразование дерева в отсортированный массив public int[] Transform(List { if (elements == null) { elements = new List } if (Left != null) { Left.Transform(elements); } elements.Add(Data); if (Right != null) { Right.Transform(elements); } return elements.ToArray(); } } //метод преобразования массива в двоичное древо private static int[] TreeSort(int[] array) { var treeNode = new TreeNode(array[0]); for (int i = 1; i < array.Length; i++) { treeNode.Insert(new TreeNode(array[i])); } return treeNode.Transform(); } Листинг исследовательской программы Полный исходный код программы выглядит следующим образом: using System; using System.Diagnostics; using System.Threading; using System.Collections.Generic; namespace SortApp { class Program { static int[] GetArray() { //Функция генерирующая массив чисел и заполняющая его случайными числами. //Размерность массива и максимальное значение указываются пользователем. //На будущее...обработать исключения... Console.WriteLine("Задайте размерность массива"); int count = Convert.ToInt32(Console.ReadLine()); int[] BaseArray = new int[count]; Random rnd = new Random(); Console.WriteLine("Введите максимальное значение для генератора случайных чисел"); int MaxValue = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Выберите метод заполнения массива чисел:"); Console.WriteLine(); Console.WriteLine("1.Упорядоченные."); Console.WriteLine("2.Обратный порядок."); Console.WriteLine("3.Вырожденные."); Console.WriteLine("4.Случайные"); Console.WriteLine("0.Выход"); int select = Convert.ToInt32(Console.ReadLine());//Получить выбор пользователя switch (select) { case 1: BaseArray[0] = MaxValue; //Индексирование массивов начинается с 0. С# for (int i = 1; i < BaseArray.Length; i++) { //Нобходимо заполнить массив таким образом, чтобы каждый последующий элемент был строго меньше предыдущего BaseArray[i] = BaseArray[i - 1] - rnd.Next(MaxValue / count) + 1; } return BaseArray; case 2: BaseArray[0] = 1; //Нобходимо заполнить массив таким образом, чтобы каждый последующий элемент был строго больше предыдущего for (int i = 1; i < BaseArray.Length; i++) { BaseArray[i] = BaseArray[i - 1] + rnd.Next(MaxValue / count) + 1; } return BaseArray; case 3: //Нобходимо заполнить массив числами от 1 до 12 for (int i = 0; i < BaseArray.Length; i++) { BaseArray[i] = rnd.Next(12) + 1; } return BaseArray; case 4: //Заполняем массим случайным образом for (int i = 0; i < BaseArray.Length; i++) { BaseArray[i] = rnd.Next(MaxValue + 1); } return BaseArray; } return BaseArray; } static int[] BubbleSort(int[] mas) //Метод пузырьковой сортировки. //В качестве параметра будем передавать сгенерированный ранее массив чисел { int temp; for (int i = 0; i < mas.Length; i++) { for (int j = i + 1; j < mas.Length; j++) { if (mas[i] > mas[j]) { temp = mas[i]; mas[i] = mas[j]; mas[j] = temp; } } } return mas; } //метод для обмена элементов массива static void Swap(ref int x, ref int y) { int t = x; x = y; y = t; } //метод возвращающий индекс опорного элемента static int Partition(int[] array, int minIndex, int maxIndex) { int pivot = minIndex - 1; for (int i = minIndex; i < maxIndex; i++) { if (array[i] < array[maxIndex]) { pivot++; Swap(ref array[pivot], ref array[i]); } } pivot++; Swap(ref array[pivot], ref array[maxIndex]); return pivot; } //быстрая сортировка static int[] QuickSort(int[] array, int minIndex, int maxIndex) { if (minIndex >= maxIndex) { return array; } int pivotIndex = Partition(array, minIndex, maxIndex); QuickSort(array, minIndex, pivotIndex - 1); QuickSort(array, pivotIndex + 1, maxIndex); return array; } static int[] QuickSort(int[] array) { //Перегруженный метод return QuickSort(array, 0, array.Length - 1); } //простая реализация бинарного дерева public class TreeNode { public TreeNode(int data) { Data = data; } //данные public int Data { get; set; } //левая ветка дерева public TreeNode Left { get; set; } //правая ветка дерева public TreeNode Right { get; set; } //рекурсивное добавление узла в дерево public void Insert(TreeNode node) { if (node.Data < Data) { if (Left == null) { Left = node; } else { Left.Insert(node); } } else { if (Right == null) { Right = node; } else { Right.Insert(node); } } } //преобразование дерева в отсортированный массив public int[] Transform(List { if (elements == null) { elements = new List } if (Left != null) { Left.Transform(elements); } elements.Add(Data); if (Right != null) { Right.Transform(elements); } return elements.ToArray(); } } //метод преобразования массив в двоичное древо private static int[] TreeSort(int[] array) { var treeNode = new TreeNode(array[0]); for (int i = 1; i < array.Length; i++) { treeNode.Insert(new TreeNode(array[i])); } return treeNode.Transform(); } static void Main(string[] args) { int[] BaseArray = GetArray(); //инициализируем неотсортированный массив int selection = -1;//Инициализация переменной выбора пункта меню Stopwatch stopWatch = new Stopwatch();//подсчет времени исполнения кода while (selection != 0)//Будем повторять пока пользователь не выйдет из программы { Console.Clear(); Console.WriteLine("Выберите пункт меню:"); Console.WriteLine(); Console.WriteLine("1.Сортировка пузырьковым методом."); Console.WriteLine("2.Быстрая сортировка."); Console.WriteLine("3.Сортировка двоичным деревом."); Console.WriteLine(); Console.WriteLine("0.Выход"); selection = Convert.ToInt32(Console.ReadLine());//Получить выбор пользователя //Выводить отсортированный массив не будем, займет много экранного места switch (selection) { case 1://Выбран 1-й пункт меню (Пузырьковая сортировка) stopWatch.Start(); int[] BubbleSortedArray = BubbleSort(BaseArray); stopWatch.Stop(); TimeSpan ts = stopWatch.Elapsed; string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:000000}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10); Console.WriteLine("RunTime " + elapsedTime); break; case 2://Выбран 2-й пункт меню (Быстрая сортировка) stopWatch.Start(); int[] QuickSortedArray = QuickSort(BaseArray); // быстрая сортировка stopWatch.Stop(); TimeSpan ts1 = stopWatch.Elapsed; string elapsedTime1 = String.Format("{0:00}:{1:00}:{2:00}.{3:000000}", ts1.Hours, ts1.Minutes, ts1.Seconds, ts1.Milliseconds / 10); Console.WriteLine("RunTime " + elapsedTime1); break; case 3: //Выбран 3-й пункт меню (Сортировка двоичным деревом) stopWatch.Start(); int[] TreeSortedArray = TreeSort(BaseArray); // быстрая сортировка stopWatch.Stop(); TimeSpan ts2 = stopWatch.Elapsed; string elapsedTime2 = String.Format("{0:00}:{1:00}:{2:00}.{3:000000}", ts2.Hours, ts2.Minutes, ts2.Seconds, ts2.Milliseconds / 10); Console.WriteLine("RunTime " + elapsedTime2); break; } } } } } Для того чтобы заполнить таблицу по методу «Пузырька», выбирать предлагаемые пункты меню, задать количество элементов для сортировки и, в том числе, виды заполнения массива: 1. «Упорядоченные» — элемент массива с меньшим индексом строго больше элемента с большим индексом; 2. «Обратного порядка» — элемент массива с меньшим индексом строго меньше элемента с большим индексом; 3. «Вырожденные» — массив заполняется случайным образом числами из диапазона от 1 до 12; 4. «Случайные» — массив заполняется случайными числами из диапазона от 1 до 70000. Аналогично проделываем для метода «Быстрой сортировки» и «Сортировки двоичным деревом». Для чистоты эксперимента будем перезапускать программу для каждого случая Полученные результаты заносим в таблицу:  Так как методы быстрой сортировки и сортировки двоичным деревом являются нестабильными и скорость работы этих алгоритмов может деградировать в зависимости от исходных данных, в частности при ранее отсортированных массивах, а при большом количестве данных приводят к переполнению стека, поэтому трудно вычислить их поведение при N элементах. По результатам таблицы построим график зависимости времени сортировки от его размеров:  Вывод На сегодняшний день существует множество алгоритмов сортировки, придумано множество решений. Однако, самого лучшего, готового для применения к любой задаче не существует. Основным критерием для выбора того или иного вида сортировки является сам блок данных, который нужно упорядочить. Алгоритм сортировки методом пузырька – простейшая и самая медленная сортировка последовательности, в которой производится последовательная замена соседних парных элементов. В сортировке по возрастанию, элементы с большим значением смещаются к концу массива, а с меньшим к началу. Обратные, вырожденные и случайные последовательности показали примерно такой же результат, зависимость примерно N^2 . Также это отражается в последовательностях свыше 32000 элементов, время обработки можно увидеть в таблице. Этот метод эффективен для сортировки массивов небольшого размера. Достоинство сортировки – это простота для понимания. Но недостаток - большие объемы данных с его помощью обработать не получится из-за большого времени. Алгоритмы быстрой сортировки и сортировки двоичным деревом – трудно назвать простыми, а из–за вложенной рекурсии при худших случаях приводят к переполнению стека. В быстрой сортировке, производится поиск опорного значения, исходный массив разбивается на две части, левую – элементы меньше опорного, и правую – элементы больше опорного. Затем происходит рекурсивное разбиение подмассивов до тех пор, пока в каждом не останется по 1 элементу. Построение двоичного дерева для сортировки – метод так же неподходящий для сортировки ранее упорядоченных данных, так как корневым элементом выбирается первое значение массива и в работе с такими данными - граф будет разбалансированным. В случае ранее упорядоченных данных метод пузырька – это «стабильный» алгоритм сортировки, что можно заметить по времени выполнения на всех последовательностях. Данный метод не превосходит по скорости методы быстрой сортировки и сортировки двоичным деревом, но при худших случаях исходного набора данных не приводит к переполнению стека. Приблизительная зависимость N^2 . При работе с неотсортированными данными метод быстрой сортировки - самый быстродействующий из вышеописанных. Этот метод также эффективен на небольших наборах данных и не требователен к дополнительной памяти. В результате проведенного исследования и полученных данных, для сортировки неотсортированного массива, наиболее оптимальным из представленных алгоритмов для сортировки массива является быстрая сортировка. Так, как скорость данного алгоритма сортировки выше, а объём потребляемой памяти меньше. | ||||||||||||||||||||