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