НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи сортування» Варіант № 15 Дата « 5 » червня 2022 Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Теоретичні відомості: Сортування – впорядковування за ключовими елементами структури даних, на якій визначено відношення порядку. Алгоритмом сортування називається алгоритм для впорядкування деяких елементів множини. Практично кожен алгоритм сортування можна розбити на три основних етапи: Порівняння (впорядкованість пари елементів), Перестановка (зміна місць пари елементів), Перестановка (власне алгоритм сортування. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основною характеристикою є час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного. Cортування вставками - cуть методу полягає в тому, що на кожному кроці алгоритму вибирається один з елементів вхідних даних і вставляється його на потрібну позицію в уже відсортованому списку, до тих пір, поки набір вхідних даних не буде вичерпаний. Сортування вибором — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку. Сортування обміном (Bubblesort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку. Та купа інших методів сортування. Завдання на лабораторну роботу: 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел / Як перше сортування було виконане сортування вставками, а для порівняння вже було написане сортування бульбашкою. Результати виконання: Розмір Час виконання(Insert sort) Час виконання(Bubble sort)  10x10 1300 нс 10300 нс  50x50 39600 нс 5721700 нс  100x100 258200 нс 93991700 нс   / / Посилання на Replit: https://replit.com/join/kllbnwxfnf-tr-15fundamient Висновок: Під час виконання даної лабораторної роботи було набуто практичних навичок з використання методів сортування, а саме, завдання було виконано за допомогою методів сортування вставкавами, там бульбашкою. Для порівняння їх між собою було складено таблицю із замірами часу сортування різного розміру матриць. Копія коду: #include <iostream> #include <chrono> #include <ctime> using namespace std; int main() { srand(time(NULL)); int matSize; cout << "Enter matrix size:\n"; cin >> matSize; int mat[matSize][matSize]; int mat1[matSize][matSize]; //input for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { mat[i][j] = rand() % 62 + (-30); } } cout << "Insert sort\n"; //output cout << "Before array: \n"; for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { cout << mat[i][j] << "\t"; } cout << endl; } auto start1 = chrono::steady_clock::now(); // insert sort for(int i = 0; i < matSize; i++) { for (int step = matSize - i - 1; step < matSize; step++) { int element = mat[i][step]; int j = step - 1; while (element < mat[i][j] && j >= matSize - i - 1) { mat[i][j + 1] = mat[i][j]; --j; } mat[i][j + 1] = element; } } auto end1 = chrono::steady_clock::now(); //output cout << "\nAfter array: \n"; for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { cout << mat[i][j] << "\t"; } cout << endl; } cout << "\nElapsed time: " << chrono::duration_cast<chrono::nanoseconds>(end1 - start1).count() << " ns\n"; cout << "\nBubble sort: \n"; //input for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { mat1[i][j] = rand() % 62 + (-30); } } //output cout << "Before array: \n"; for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { cout << mat1[i][j] << "\t"; } cout << endl; } auto start2 = chrono::steady_clock::now(); //bubble sort int temp1; for(int i=0; i<=matSize*matSize; i++) { for(int k=0; k<matSize; k++) { for(int j=matSize-1-k; j<matSize-1; j++) { if(mat1[k][j]>mat1[k][j+1]) { temp1=mat1[k][j]; mat1[k][j]=mat1[k][j+1]; mat1[k][j+1]=temp1; } } } } auto end2 = chrono::steady_clock::now(); //output cout << "\nAfter array: \n"; for(int i = 0; i < matSize; i++) { for(int j = 0; j < matSize; j++) { cout << mat1[i][j] << "\t"; } cout << endl; } cout << "\nElapsed time: " << chrono::duration_cast<chrono::nanoseconds>(end2 - start2).count() << " ns\n"; }