Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ СОРТУВАННЯ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №3
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
МЕТОДИ СОРТУВАННЯ
Варіант №12
Київ 2022
Мета:
Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування.
Теоретична частина
Сортування масиву — один з найбільш розповсюджених процесів обробки даних. Завдяки йому здійснюється розміщеня об’ектів у визначеному порядку, наприклад, чисел за зростанням або за спаданням їх значень, прізвищ у алфавітному порядку тощо. Існують різні методи сортування, серед них — обмінне сортування (метод «пухирця», «шейкер-сортування), сортування вибором, сортування вставками, швидке сортування, сортування Шелла, пірамідальне сортування, сортування обчисленням адреси, сортування порозрядним групуванням тощо. Ці методи відрізняються швидкістю отримання результату, складністю і універсальністю.
Розглянемо три методи сортування: обміном, вибором та вставками. Названі методи легко описуються у формі чітких алгоритмiв і передбачають нескладну програмну реалізацію, крім того вони цікаві тим, що моделюють природну поведінку людини, яка здійснює сортування вручну. З іншого боку, вказані методи не досить ефективні і використовуються у випадках, коли необхідно відсортувати масиви невеликого розміру.
Обмінне сортування проілюструємо простим сортуванням обмiном — методом «пухирця», який здійснюється шляхом перестановки елементів за визначеним правилом.
Головні складові методу «пухирця»:
крок сортування містить перегляд елементів масиву з початку до кінця, при цьому розглядаються пари сусідніх елементів;
елементи деякої пари міняються місцями у випадку, коли їх послідовність розташування не відповідає умові сортування (за зростанням або за спаданням).
Сортування за вставками
Ще один алгоритм, розроблений для впорядкування масивів, - алгоритм сортування вставок. Даний алгоритм (як і інші розглянуті на нашому сайті) досить простий. Він складається з двох циклів (один вкладений в межах іншого). Перший цикл робить прохід через масив, а другий - рух оброблюваних елементів.
Часова складність
Розмір
Складність алгоритму
Час роботи методом вставок
Час роботи методом бульбашки
10х10
O(n^2)
Квадратичний алгоритм
1,25e-05
9,07e-0,6
50х50
5,531e-0,5
0,00401715
100х100
0,0108855158
0,0790612
Завдання:
Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму.
Завдання до Варіанту_12
Метод сортування вставками
+Метод сортування бульбашка (за бажанням)
Результати виконання лабораторної роботи:
Код:
//Лабораторна робота №3_ПСА
//ТР-15_Ткаченко_Майя, Варіант_12
#include <iostream>
#include <algorithm>
#include "chrono"
using namespace std;
Висновки
В ході виконання даної лабораторної роботи було розглянуто різні методи сортування масивів. Виконано завдання згідно варіанту, проведено сортування по схемі, методом вставок, а також в якості методу сортування за бажанням, було вибрано метод бульбашки. Також програма виводить окремо час виконання кожного алгоритму.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора