Капралов Курсовая работа. Сортировка массива методом слияния
 Скачать 0.53 Mb.
|
|
Карагандинский Технический Университет Кафедра ИТБ КУРСОВАЯ РАБОТА По дисциплине Практикум по программированию С++_____________ Тема: Сортировка массива методом слияния
Караганда 2021 Карагандинский Технический УниверситетФакультет ФИТ "УТВЕРЖДАЮ"Кафедра ИТБ Зав. Кафедрой ________________(подпись)"___" ________ 20___г.ЗАДАНИЕ НА КУРСОВУЮ РАБОТУпо дисциплине Практикум по программированию С++Студенту Капралову Сергею Алексеевичу группы СИБ 20-3Тема Сортировка массива методом слиянияИсходные данные:____________________________________________________________ _____________________________________________________________________________ _____________________________________________________________________________ _____________________________________________________________________________ Задание выдано " 21 " января 2021 г.Руководитель подписьСтудент подписьСодержания Введение……………………………………………………………….……….4 1. Теоретическая часть 1.1 Основные понятия……………..………………………………………..5 1.2. Классификация элементов алгоритма сортировки……………….6 1.3. Характеристика методов сортировки…………………………8 Практическая часть (вариант № 5) 2. Задание…………………………………………………………………11 3. Тестирование программы…………………………………………...11 Таблица времени сортировки …………………………………………..13 Заключение………………………………………………………………...13 Список литературы ……………………………………………………14 Приложение А листинг программы…………………………………….15 Приложение Б Антиплагиат …………………………………………….20 Введение Актуальность Информационные технологии появились в нашем мире совсем недавно. Несколько лет назад люди даже не подумали бы, что можно будет общаться на расстоянии, видя друг друга, заказывать еду, одежду, оборудование и т. д., Изучать языки или другие виды деятельности. Но новые информационные технологии породили ряд проблем, так как любая информация может стать отличным товаром для мошенников. Многие компании готовы отдать большие деньги, чтобы узнать секреты конкурентов. Поэтому утечка информации в наше время является главной проблемой компаний, банков и т.д. Информационная безопасность – одно из самых главных навыков 21 века, а работа с любой информацией станет легче, если её отсортировать. С помощью сортировки можно решать различные виды задач. Сортировка может понадобиться, когда нужно отобразить визуально распределение данных. Для разных данных мы должны выбирать определенные методы сортировки для повышения производительности и скорости сортировки. Хоть рассматриваемые в данном варианте работы сортировки являются простыми и не очень эффективными, но они тоже имеют преимущества и также лежат в основе других сортировок. Сортировки вставками, пузырьком, выбором и т.д. в силу своей простоты являются очень эффективными для изучения свойств большинства принципов сортировки, они легки для понимания и не очень длинные. Хоть сложные алгоритмы требуют меньшего числа операций, но являются более сложными для понимания и алгоритмизации. Поэтому простые сортировки более эффективны для данных с малым количеством элементов и работают относительно быстро. Разработкой программного обеспечения занимается отрасль науки под названием программирование. Программирование это процесс создания компьютерных программ. По выражению одного из основателей языков программирования Никлауса Вирта, «Программы = алгоритмы + структуры данных». Программирование основывается на использовании языков программирования. Программирование имеет ряд важных задач. Одной из важных задач для программирования является задача сортировки. Цель: Изучить теоретические основы различных методов сортировок и области их применения. Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно заполняется случайными числами. Добавить возможность предварительной сортировки начальных серий методом простой вставки. Провести статистические наблюдения над временем работы сортировки слиянием: без предварительной сортировки начальных серий; с отсортированными начальными сериями, размером 8, 16 элементов. Время подготовки начальных серий также учитывается при замере. Выбор варианта статистического наблюдения вводится с клавиатуры. Задачи: изучить теоретические основы различных методов сортировок и области их применения; разработать программу, выполняющую сортировку массива методом слияния; разработать команды позволяющие заполнить массив предварительно случайными числами; разработать и добавить возможность предварительной сортировки начальных серий методом простой вставки; провести статистические наблюдения над временем работы сортировки слиянием без предварительной сортировки начальных серий; провести статистические наблюдения над временем работы сортировки слиянием с отсортированными начальными сериями, размером 8, 16 элементов; при проведении статистических наблюдений учитывать время подготовки начальных серий при замере; выбор варианта статистического наблюдения вводить с клавиатуры. 1. Теоретическая часть. 1.1. Основные понятия Сортировка это последовательное расположение или разбиение на группы чего-либо в зависимости от выбранного критерия. Сортировка входит в одну из важных задач, потому что облегчает работу с большими числами, работу с поиском и т.д. существует множество методов сортировки, каждый из которых имеет свои достоинства и недостатки. На данный момент существует большое количество алгоритмов сортировки, а выбор алгоритма зависит от задачи и структуры сортируемых данных. Рассмотрим некоторые сортировки: Сортировка пузырьком. Сортировка перемешиванием. Сортировка методом вставок. Сортировка подсчетом. Сортировка слиянием. Цифровая сортировка. Сортировка методом выбора. Сортировка методом Шелла. Обменная поразрядная сортировка. Пирамидальная сортировка. Сортировка массивом (хеширование). Быстрая сортировка (метод Хоара). Блочная сортировка. За данный семестр мы успели разобрать такие сортировки как сортировка «пузырьком», сортировка «вставками», сортировка «слиянием», сортировка «выбором» и сортировка «Шелла». Время сортировки - основной параметр, характеризующий быстродействие алгоритма. Память - место которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы. Алгоритм - это последовательность действий, которую необходимо выполнить для решения задачи. Сортировка - это последовательное расположение или разбиение на группы чего-либо в зависимости от выбранного критерия. Любой алгоритм сортировки можно разделить на несколько частей: 1. сравнение 2. перестановка В любом алгоритме сортировки есть сравнение и перестановка, отличаются сортировки затратой памяти, временем и алгоритмами. 1.2. Классификация элементов алгоритма сортировки Написание любого алгоритма имеет несколько важных свойств: 1. определённость 2. массовость 3. результативность 4. дискретность Определённость алгоритма значит, что алгоритм должен быть понятен любому пользователю, и он смог его повторить. Массовость отвечает за предназначение алгоритма для решения класса задач. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов. Дискретность алгоритма означает, что алгоритм исполняется по шагам, то есть каждое новое действие алгоритма должно исполняться только после того, как предыдущее действие закончило свою задачу. Как можно представить алгоритм: 1. Алгоритм можно представить словесно,  2. В виде схемы будь то просто картинка или гиф изображение, что даже лучше,  3. Можно показать программой на языке программирования,  4. В словесно-аналитической форме. Какие виды алгоритмических структур бывают? 1. Линейный - все команды исполняются последовательно. 2. Разветвляющийся - действия происходят в зависимости от условия, работает либо одна серия команд, либо другая. 3. Циклический - повторяется некоторый участок алгоритма Сфера применения Внутренняя сортировка - работа с массивом данных, целиком расположенном в памяти и возможным доступом к его любому элементу. Внешняя сортировка - характеризуется работой с данными большого объема и последовательным доступом к отдельным элементам списка. Применяется, например, при упорядочении файлов. 1.3. Характеристика алгоритмов сортировки: Сортировка пузырьком. Сортировка пузырьком (от англ. bubble sort) является самой популярной сортировкой, простой алгоритм и запоминающееся название. Но также она является и самой худшей сортировкой. Алгоритм заключается в том, что мы берем пару чисел, которые стоят рядом и меняем их местами, если элемент с меньшим индексом больше элемента с большим индексом. Алгоритм продолжается пока есть такие элементы, а остановится сортировка, когда такие элементы закончатся. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.  Сортировка вставками. Сортировка вставками (от англ. insertion sort) алгоритм сортировки, элементы которой просматриваются по одному, каждый последующий элемент размещается в нужное место ранее упорядоченных элементов. Вначале отсортированная последовательность будет пуста. На каждом шаге один элемент входных данных помещается на нужную позицию в отсортированной последовательности до того пока набор данных не будет исчерпан.  Сортировка слиянием. Сортировка слиянием (от англ. merge sort) алгоритм сортировки для упорядочивания списков или других структур данных доступ к которым можно получать исключительно последовательно. Сортировка слиянием это отличный пример принципа “разделяй и властвуй”. Для начала задача разбивается на несколько подзадач. После эти задачи решаются рекурсивным вызовом (Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.) или непосредственно, если имеют небольшой размер. После всех действий их решения комбинируются, и получается исходное решение.  Сортировка выбором. Сортировка выбором (от англ. Selection sort) алгоритм сортировки, который может быть как устойчивым, так и неустойчивым. Действия алгоритма: 1. должны найти номер минимального значения в нужном нам списке. 2. меняем значения позиций минимального значения на значение первой, не отсортированной позиции (не меняем, если минимальный элемент уже находится на данной позиции) 3. сортируем хвост нашего списка, исключая уже отсортированные элементы  Сортировка шелла. Сортировка шелла (от англ. Shell sort) – усовершенствованная версия алгоритма сортировки методом вставок. Метод шелла сравнивает элементы стоящие не только рядом, но и на расстоянии друг от друга. Работа сортировки шелла заключается в том, что сначала сравниваются и сортируются значения, стоящие на некотором расстоянии друг от друга. После те же действия повторяются для некоторых меньших значений, а завешается сортировка Шелла упорядочиванием элементов (то есть обычной сортировкой вставками).  Практическая часть 2. Задание Сортировка массива методом слияния Цель работы: Разработать программу, выполняющую сортировку массива методом слияния. Массив предварительно заполняется случайными числами. Добавить возможность предварительной сортировки начальных серий методом простой вставки. Провести статистические наблюдения над временем работы сортировки слиянием: без предварительной сортировки начальных серий; с отсортированными начальными сериями, размером 8, 16 элементов. Время подготовки начальных серий также учитывается при замере. Выбор варианта статистического наблюдения вводится с клавиатуры. В процессе работы были созданы две функции для работы сортировки методом “вставок” и сортировки методом “слияния”. 3. Тестирование программы и сортировки методом слияния в разных случаях на время работы Для работы было разработано 2 функции сортировки вставок (по 8 элементов и по 16 элементов) разработана функция сортировки слияния. В данной программе использовалась функция для подсчёта тиков (для более точного подсчёта сортировка была внесена в цикл на 100000 повторений) QueryPerformanceCounter находящаяся в библиотеке “Windows.h”. Размер массива вводится в консоли, заполнение массива идёт с помощью rand(), а дальше пользователь выбирает метод сортировки. Отчёт на работоспособность программы Для начала вводим размер массива (количество элементов в списке)  Ввели размер массива на 32 элемента, дальше нас просят выбрать метод. Так как все сортировки были внесены под цикл на 100000 повторений, делим 573,399/100000 = 0,00573399  571,408 / 100000 = 0,00571408  572,517/100000 = 0,00572517 Выход из программы производится вводом любого символа, чтобы продолжить требуется нажать «+». Для более точного отслеживания были проверены все сортировки на время работы с разным количеством элементов и данные записаны в таблицу ниже Таблица времени сортировки
Смотря на таблицу можно сделать вывод, что сортировка слиянием с предварительной сортировкой вставками по16 и по 8 элементов делают сортировку быстрее, но не всегда. В программе, где массив на 48, 96, элементов видно, что сортировка слиянием справилась быстрее с обычным не отсортированным предварительно массивом, нежели с отсортированными массивами. Заключение В ходе курсовой работы прошел анализ и оценка имеющихся алгоритмов сортировки и был сделан вывод, что технологии сложноватых сортировок (сортировки использующие повторение массива), больше результативны, нежели технологии бесхитростных сортировок. Была разработана программа с функциями сортировки простых вставок по 8 и 16 элементов для предварительной сортировки перед сортировкой слиянием и проверки на скорость сортировки методом слияния. Массив с задаваемым количеством элементов, который был отсортирован всеми методами указанными в курсовом варианте и проверен по времени работы. С помощью данного приложения был проведен экспериментальный анализ сортировок методом слияния, слияния с предварительной сортировкой вставками по 8, слияния с предварительной сортировкой вставками по 16 элементов. По данным экспериментального анализа в среднем сортировка методом слияния с предварительной сортировкой по вставками по 16 элементов занимает меньше времени, чем обычная сортировка слиянием. Список Литературы 1. https://studrb.ru/works/entry9551 2. https://ru.wikipedia.org/wiki/Сортировка_пузырьком 3. https://ru.wikipedia.org/wiki/Сортировка_слиянием 4. https://ru.wikipedia.org/wiki/Сортировка_вставками 5. https://ru.wikipedia.org/wiki/Сортировка_выбором 6. https://ru.wikipedia.org/wiki/Сортировка_Шелла 7. https://academy.yandex.ru/posts/osnovnye-vidy-sortirovok-i-primery-ikh-realizatsii 8. https://habr.com/ru/post/335920/ Приложение А Листинг программы #include #include using namespace std; double PCFreq = 0.0; __int64 CounterStart = 0; void StartCounter() { LARGE_INTEGER li; if (!QueryPerformanceFrequency(&li)) cout << "QueryPerformanceFrequency failed!\n"; PCFreq = double(li.QuadPart) / 1000; QueryPerformanceCounter(&li); CounterStart = li.QuadPart; } double GetCounter() { LARGE_INTEGER li; QueryPerformanceCounter(&li); return double(li.QuadPart - CounterStart) / PCFreq; } // функция сортировки вставками по 16 элементов void in_sort16(int* a, int n, int R, int L, int k = 0) { L = 16 * k; R = 16 * (k + 1) - 1; for (int i = L; i < R + 1; i++) { int t = a[i], j; for (j = i - 1; j >= L && t < a[j]; j--) { a[j + 1] = a[j]; } a[j + 1] = t; } } // функция сортировки вставками по 8 элементов void in_sort8(int* a, int n, int R, int L, int k = 0) { L = 8 * k; R = 8 * (k + 1) - 1; for (int i = L; i < R + 1; i++) { int t = a[i], j; for (j = i - 1; j >= L && t < a[j]; j--) { a[j + 1] = a[j]; } a[j + 1] = t; } } // функция сортировки слиянием void mergeSort(int* a, int n) { int step = 1; // шаг разбиения последовательности int* temp = (int*)malloc(n * sizeof(int)); // дополнительный массив while (step < n) // пока шаг меньше длины массива { int index = 0; // индекс результирующего массива int l = 0; // левая граница участка int m = l + step; // середина участка int r = l + step * 2; // правая граница участка do { m = m < n ? m : n; // сортируемый участок не выходит за границы последовательности r = r < n ? r : n; int i1 = l, i2 = m; // индексы сравниваемых элементов for (; i1 < m && i2 < r; ) // пока i1 не дошёл до середины и i2 не дошёл до конца { if (a[i1] < a[i2]) { temp[index++] = a[i1++]; } // заполняем участок результирующей последовательности else { temp[index++] = a[i2++]; } } // Или i1 < m или i2 < r - только один из операторов while может выполниться while (i1 < m) temp[index++] = a[i1++]; // заносим оставшиеся элементы сортируемых участков while (i2 < r) temp[index++] = a[i2++]; // в результирующий массив l += step * 2; // перемещаемся на следующий сортируемый участок m += step * 2; r += step * 2; } while (l < n); // пока левая граница сортируемого участка - в пределах последоватльности for (int i = 0; i < n; i++) // переносим сформированный массив обратно в a a[i] = temp[i]; step *= 2; // увеличиваем в 2 раза шаг разбиения } } int main() { setlocale(LC_ALL, "rus"); int size; cout << "введите размер массива: "; cin >> size; int* arr = new int[size]; // создаем массив //для сортировки вставками по несколько элементов-->> int R = 0, L = 0; int kon; //<<----. //для свитча-->> int switchz = 0; char ss; // для while пока ss не будет равно + свитч будет продолжаться //<<--. do { cout << "\nМассив заполнен"; for (int i = 0; i < size; i++) { arr[i] = rand() % 10; // заполняем массив } cout << "\nМетоды сортировки..." << endl << "1. Сортировка слияние с предварительной сортировкой вставками по 8 элементов" << endl << "2. Сортировка слияние с предварительной сортировкой вставками по 16 элементов" << endl << "3. Сортировка слиянием" << endl << "выберите метод: "; cin >> switchz; switch (switchz) { case 1: cout << "вы выбрали сортировку слиянием с предварительной сортировкой вставками по 8 элементов\n"; kon = size / 8; for (int k = 0; k < kon; k++) { in_sort8(arr, size, R, L, k); } //начало подсчёта StartCounter(); for (int i = 0; i < 5000000; i++) { mergeSort(arr, size); } //Sleep(1000); //вывод тиков cout << endl << "сортировка прошла за: " << GetCounter() << " кол-во тиков" << "\n"; break; case 2: cout << "вы выбрали сортировку слиянием с предварительной сортировкой вставками по 16 элементов\n"; kon = size / 16; for (int k = 0; k < kon; k++) { in_sort16(arr, size, R, L, k); } //начало подсчёта StartCounter(); for (int i = 0; i < 5000000; i++) { mergeSort(arr, size); } //Sleep(1000); //вывод тиков cout << endl << "сортировка прошла за: " << GetCounter() << " кол-во тиков" << "\n"; break; case 3: int tickcache3; cout << "вы выбрали сортировку слиянием"; //начало подсчёта StartCounter(); for (int i = 0; i < 5000000; i++) { mergeSort(arr, size); } //Sleep(1000); //вывод cout << endl << "сортировка прошла за: " << GetCounter() << " кол-во тиков" << "\n"; break; default: std::cout << "ERROR!!!!" << std::endl; break; } cout << "продолжить? (да = +) (выход = любой символ): "; cin >> ss; } while (ss == '+'); //пока ss = + system("pause"); return 0; } Приложение Б Антиплагиат  |