Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
МЕТОДИ СОРТУВАННЯ
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №3
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «МЕТОДИ СОРТУВАННЯ»
Варіант № 16
Дата «02» травень 2022
Київ 2022
Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування
Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритм.
Варіанти індивідуальних завдань
1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням).
2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3.Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел.
Завдання:
Метод сортування вставками для 16 варіанту.
/
рис 1.
Теоретичні відомості:
What is the Quick Sort Program in C?
The main process in a quicksort algorithm is partitioning. If x is the pivot in an array, then the main intent of the sorting process is to put x at the right position in a sorted array, such that smaller elements precede x and greater elements follow it.
Once the pivot element has been selected, the elements smaller than the pivot element are placed before it, and the greater ones after. There are several variations of the quick sort algorithm, depending on what kind of element (or number) is selected as the pivot:
The first element as the pivot
The last element as the pivot
A random element as the pivot
Median as the pivot
Метод сортування вставками.
Головна ідея метода є у тому, що при додавання нового елементу до вже отсортуваного масиву його треба вставити на потрібне міце, замість того щоб ставити його у довільне, і потім заново сортирувати усю послідовність.
сортування вставками має велику вичіслювальну складність. Тому вона ефективна на невеликих наборах даних. Рекомендується використовувати цей метод на наборах до десятків елементів. сортування вставками ефективна на послідовностях з даними, які вже частково відсортовані.
Хід роботи:
Написано програмний код, який виконує завдання різними способами на вибір, або за допомогою метода сортивування вставками або методом швидкого сортування. Для цього було створено два метода.
Було проведено оцінку часової складності алгоритму та порівняно час роботи та кількість ітерацій з різною для різної кількості елемнтів матриці(10, 50, 100, 500). Оцінку часу роботи наведено нижче у вигляді таблиці та графіку.
Було створенно метод для полегшення метода main, у якому відбувалося наповнення матриці випадковими числами(getMatrix). цей метод можна спростити до 2n^2+9n+4 = Θ(n^2).
Метод InsertionSort має цикл в циклі тому перший цикл буде 4+2n, потім йде 3 ітерації в циклі це 3n, Далі цикл у циклі з двома ітерації перевірки кожен раз і ще дві ітераціїї тому це можна звести до 4n^2. Загалом звести метод можна до 4+2n+3n+4n^2=4n^2+5n+4 = Θ(n^2).
Метод quickSort має в найгіршому випадку для вхідного масиву з n елементів час роботи, дорівнює Θ(n 2 ). Дивлячись на таку повільну роботу в найгіршому випадку, цей алгоритм на практиці часто є оптимальним через те, що у середньому час його роботи набагато краще: Θ(n lg n)
Підрахуємо ітерації: Ми маємо два цикли які виконуються n/2 раз, в кожному циклі по одній ітерації, тому можна сказати що вони разом буть 4*n/2=2n; Оскільки цей метод є рекурсивним, далі є формування рекурсії: в найгыршому випадку ми будемо перевіряти n разів, тому можна звести до 2n*n.
Загалом метод можна звести до 2n^2+2n= Θ(n^2).(як і було сказано вище)
Загалом завдання має такі ітераці: Цикл for тобто 4+2n ітерацій у ньому одна ітерація(виділення пам’яті для динамічного масиву); потім ще один цикл тому це буде (4+2n+1)^n і вже потім один з двох варіантів сортування також у цьому циклі тому ці методи будуть метод*n разів.
Отож, якщо повністю звести завдання до формули буде:
З InsertionSort: 2n^2+9n+4+4n^2+5n+4=6n^2+16n+12= Θ(n^2).
З quickSort: 2n^2+9n+4+2n^2+2n=4n^2+11n+4= Θ(n^2).
З InsertionSort:
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
772
0.004 msec
50
15812
0.04 msec
100
61612
0.186 msec
500
1508012
8.432 msec
З quickSort:
Розмір
Складність
Кілкість ітерацій
Час виконання
10
Θ (N)
514
0.006 msec
50
10554
0.056 msec
100
41104
0.235 msec
500
1005504
6.095 msec
/
Код програми:
Посилання на код:
https://replit.com/join/lydrsxqjmc-tr-15khavkin
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void getMatrix(int size, int mat[size][size], int mat2[size][size]){//Метод для заповнення матриці
srand(time(NULL));
int ran;
for(int i=0; i<size;i++){
for(int j=0;j<size;j++){
ran = rand() % 61 - 30; //Генерація випадкого числа від -30 до 30
mat[i][j]=ran;
mat2[j][i]=mat[i][j];
}
}
}
void InsertionSort(int n, int *mass){
int newEl, loc;
for (int i = 1; i < n; i++) {
newEl = mass[i];
loc = i - 1;
while(loc >= 0 && mass[loc] > newEl) {
mass[loc+1] = mass[loc];
loc = loc - 1;
}
mass[loc+1] = newEl;
}
}
void quickSort(int *a, int N) {
int i = 0, j = N-1;
int temp, p;
p = a[ N>>1 ];
do {
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while ( i<=j );
if ( j > 0 ) quickSort(a, j);
if ( N > i ) quickSort(a+i, N-i);
}
int main(void) {
int n,x,s,V,K;
printf("\nВедіть n: ");
scanf("%d", &n);
printf("\nОберіть яким способом опрацювати матрицю\n1 - Методом вставки(за варіантом)\n2 - Методом швидкого сортування\nВведіть 1 або 2: ");
scanf("%d", &V);
int array[n][n],perev[n][n];
getMatrix(n,array,perev);
printf("\nПервісна матриця\n");
for(int i=0; i<n;i++){
for(int j=0;j<n;j++){
printf("\t%i\t", array[i][j]);
}
printf("\n");
}
clock_t ttime1,ttime2;
ttime1 = clock();
int **array2;
array2=(int**)malloc(n * sizeof(int*));
for (int i=0; i < n; i++){
array2[i]=(int*)malloc((n)*sizeof(int));
for(int j=0;j<n;j++){
array2[i][j]=perev[i][j];
}
switch(V){
case 1:
InsertionSort(n-i,array2[i]);
break;
case 2:
quickSort(array2[i],n-i);
break;
}
}
ttime2 = clock();
printf("\n\nОпрацьована матриця\n");
for(int i=0; i<n;i++){
for(int j=0;j<n;j++){
array[i][j]=array2[j][i];
printf("\t%i\t", array[i][j]);
}
printf("\n");
}
printf("\nTime of task: %lf msec", (double)(ttime2-ttime1)/CLOCKS_PER_SEC*1000);
}
Результат програми: / /
Висновок: У цій лабораторної роботі ознайомилися з меотдами сортування масивів. Перевірили варіанти розв’язання завдання на часову складність і кількість ітерацій. Знайшли підтвердження теорію у тому що Insertion Sort не підходить до сортування великих масивах, і тому в них Quick Sort є доцільнішим і швидшим. Для маленьких обсягів масиву розбіжність невелика. Зроблено звіт до лабораторної роботи та надіслано викладачу.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора