НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Сортування» Варіант 18 Мета: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Теоретична частина Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів. Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є: Час, необхідний на впорядкування n-елементного масиву. Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є — це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритмизазвичай є стабільними, хоча і не ефективними для великих масивів. Інший клас алгоритмів здійснює впорядкування за час . В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного. Необхідність додаткової пам'яті для сортування. Зазвичай необхідно O(1) пам'яті. Стабільність (англ. Stability) — стабільне сортування не змінює взаємного розташування елементів з однаковими ключами. За час : Сортування вибором — (англ. Selectionsort) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку. Сортування вставкою(включенням) — (англ. Insertionsort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди. Сортування обміном (сортування бульбашкою, англ. Bubblesort) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел. Метод сортування вставками / Блок-схема // Оцінка складності Розмір Складність Час виконання вставкою Час виконання вибором  10x10  O(N^3) 1.9e-04 2.4e-04  50x50  3.2e-04 4.3e-04  100x100  8.9e-04 9.7e-04   Результат роботи / / Висновок: Було написано програму, що сортує задану матрицю двома різними методами (вставки та вибору) згідно з індивідуальним завданням та виводить результат на екран. Проведено порівняння між швидкостями роботи обох методів, сортування вставкою відбувалось швидше. Програмний код https://replit.com/join/imgikrmwdq-okseniait #include <stdio.h> #include <math.h> #include <time.h> int main(void) { clock_t start = clock(), diff; int L=10; int arr1[L][L]; int arr2[L][L]; int i, j, k, t, n; for(i=0; i<L; i++){ for(j=0; j<L; j++){ arr1[i][j]=rand()%50; arr2[i][j]=arr1[i][j]; } } for(i=0; i<L; i++){ for(j=0; j<L; j++){ printf("%d \t", arr1[i][j]); } printf("\n"); } printf("\n"); //// int arr[L]; for(j=0; j<L; j++){ arr[j]=rand()%50; } /////////////// vstavka for(k=0; k<L; k++){ for (i=1; i<L-k; i++){ t = arr1[k][i]; for (j=i-1; j>=0 && arr1[k][j]>t; j--){ arr1[k][j+1] = arr1[k][j]; } arr1[k][j+1] = t; } } /*diff = clock() - start; int msec1 = diff * 1000000 / CLOCKS_PER_SEC;*/ ////////////////vybor for (n=0; n<L; n++){ for (i=0; i<L-n; i++){ k=i; t=arr2[n][i]; for (j=i+1; j<L-n; j++){ if(arr2[n][j]<t){ k=j; t=arr2[n][j]; } } arr2[n][k]=arr2[n][i]; arr2[n][i]=t; } } printf("Методом вставок\n"); for(i=0; i<L; i++){ for(j=0; j<L; j++){ printf("%d \t", arr1[i][j]); } printf("\n"); } printf("\nМетодом вибору\n"); for(i=0; i<L; i++){ for(j=0; j<L; j++){ printf("%d \t", arr2[i][j]); } printf("\n"); } diff = clock() - start; int msec1 = diff * 1000000 / CLOCKS_PER_SEC; printf("\nЧас виконання: %d мікросекунд \n", msec1%1000); return 0; }