Отчет. Алгоритмы сортировки и оценка их сложности
 Скачать 222.63 Kb.
|
|
Министерство образования Российской Федерации Государственный Университет Институт Кафедра Отчет По дисциплине: «Языки программирования» На тему: «Алгоритмы сортировки и оценка их сложности» Выполнил: студент 1 курса, Проверил: , 2019. Содержание лабораторная работа № 10 3 Задание № 1 3 Задание № 2 3 Задание № 3 3 Задание № 4 5 лабораторная работа № 10 Задание № 1 Напишите программу, которая выполняет следующие функции: – Генерацию элементов массива с заданной размерностью; – Сортировку массива каждым из 6 способов (пузырьковая сортировка, сортировка вставкой, сортировка выбором, быстрая сортировка, сортировка слиянием, шейкерная сортировка); – Осуществляет подсчет времени сортировки и количества перестановок. Язык программирования: С++. Среда разработки: Microsoft Visual Studio 2019 v16.0.3. Платформа решения: x64. Задание № 2 Провести эксперимент сортировки массива со следующим количеством элементов: 1'000, 10'000 и 100'000. Для проведения эксперимента необходимо произвести по 5 запусков каждого алгоритма и выбрать наилучшее время. Выбранный наилучший результат занести в таблицу. Сортировку осуществлять с одним и тем же набором данных. Таблица 1. Результаты эксперимента.
Задание № 3 Оцените сложность каждого алгоритма и сделайте вывод о наилучшем способе сортировки массива по каждой размерности массива. Свой ответ поясните. С начала хотелось бы кратко описать каждый из представленных алгоритмов: Сортировка пузырьком (от англ. Bubble sort) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность настоящего алгоритма равно  .Сортировка выбором (от англ. Selection sort) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске наименьшего элемента массива и перемещении его в начало. Сложность настоящего алгоритма равно .Сортировка вставками (от англ. Insertion sort) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получается отсортированный массив. Сложность настоящего алгоритма равно .Быстрая сортировка (от англ. Quick sort) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получается отсортированный массив. Среднее значение настоящего алгоритма равно  .Сортировка слиянием (от англ. Merge sort) – этот алгоритм упорядочивает списки (или другие структуры данных, доступ к элементам, которых можно получать только последовательно) в определенном порядке. Слияние означает объединение двух и более последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, в результате чего массив упорядочивается. Среднее значение настоящего алгоритма равно .Шейкерная сортировка (от англ. Cocktail sort) – она же сортировка перемешиванием, она же двунаправленная сортировка – по сути всего лишь оптимизированный алгоритм сортировки пузырьком (см. выше). В ее основе также лежит сравнение двух соседних элементов. Единственное отличие состоит в том, что теперь это происходит в двух направлениях поочередно, постепенно сужая диапазон сортировки. В итоге за один проход в конец массива «всплывает» наибольший элемент из диапазона, а за следующий проход – в начало массива наименьший (при сортировке по возрастанию). Эти элементы можно больше не рассматривать и таким образом диапазон сужается с двух сторон. Шейкерная сортировка работает быстрее, чем сортировка пузырьком, но все еще имеет сложность .Оценить сложность алгоритмов нагляднее всего можно в виде таблицы и графика (для сравнения в ней представлены также некоторые другие виды сортировок): Таблица 2. Сравнение временной сложности алгоритмов сортировки.   Рисунок 1. График временной сложности алгоритмов сортировки.  Выводы: в результате проведенного эксперимента выяснилось, что наиболее эффективным из представленных алгоритмов является быстрая сортировка, которая полностью оправдывает свое название. Имея незначительную разницу во времени при упорядочивании небольших массивов (до 1'000 элементов), она проявляет весь свой потенциал при работе с большими массивами данных (свыше 10'000 элементов), что является ключевым преимуществом при работе в крупных проектах. Сортировка слиянием при упорядочивании небольших массивов (до 1'000 элементов) демонстрирует хорошие показатели, однако при сортировке массивов среднего и большого объема (свыше 10'000 элементов) она показывает неудовлетворительные результаты. Сортировки пузырьком, выбором и вставками имеют схожие алгоритмы работы и показывают неудовлетворительные результаты с массивами любой разрядности. Самым медленным способом сортировки является шейкерная. Она показывает худшие результаты в массивах любой размерности и к работе с коммерческими проектами категорически не допускается. Задание № 4 Оформите отчет, который должен содержать: – Описание алгоритмов сортировки в виде блок-схемы и ее описанием; – Реализацию этих алгоритмов на языке программирования C++; – Описание компьютера на котором проводился эксперимент (вид процессора, тактовая частота, количество ядер, количество оперативной памяти и т. д.); – Результаты эксперимента в виде таблицы; – Вывод по каждой размерности массива с указанием лучшей сортировки и пояснениями. Блок-схема находится в папке с программой. Характеристика испытательного стенда: ЦПУ AMD Athlon 64 X2, 4600+, 2.4 GHz. ОЗУ Kingston, DDR2, 800 MHz (PC-6400), 2 x 4 GB. МП ASUS M2N-E (N-F570U, DDR 2, PCI-E, SATA, USB 2.0). ВК ASUS ATI 2600PRO DDR2, 256 MB, 128 bit. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||