Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Сортування
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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;
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора