Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та моделі обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
до лабораторної роботи № 1
з дисципліни «Алгоритми та моделі обчислень»
Варіант: 24
Львів 2022
Мета: проаналізувати складність заданих алгоритмів.
Завдання: скласти програму, яка дозволяє провести порівняння двох алгоритмів за характеристикою часової складності.
Блок-схеми
/
/
Код програми
Варіант 4
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define SIZE 10000
//Варіант 4:Порівняння алгоритмів сортування бульбашкою і швидке сортування
void bubbleSort(int arr1[], int size)
{
for (int i = 0; i<SIZE - 1; i++){
for(int j = SIZE - 1; j > i; j--){
if (arr1[j] < arr1[j - 1]){
std::swap(arr1[j], arr1[j-1]);
}
}
}
}
void QuickSort(int arr2[], int first, int last)
{
int middle = arr2[(first + last) / 2];
int i = first;
int j = last;
do {
while (arr2[i]< middle)
i++;
while(arr2[j]> middle)
j--;
if (i<= j){
std::swap(arr2[i], arr2[j]);
i++;
j--;
}
} while(i<= j);
if(j> first)
QuickSort(arr2, first, j);
if(i< last)
QuickSort(arr2, i, last);
}
void Initialize(int arr[], int size){
for (int i= 0; i< size; i++){
arr[i]= rand() % 1000;
}
}
void printArrayTime(int* array, double time)
{
cout << time << "\n";
}
int main(){
double k= clock() != -1 ? clock() : 0;
int arrBuble[SIZE], arrQuick[SIZE];
Initialize(arrBuble, SIZE);
arrQuick[SIZE]= arrBuble[SIZE];
double start_time=0, end_time=0;
start_time = clock() != -1 ? clock() : 0;
bubbleSort(arrBuble, SIZE);
end_time = clock() != -1 ? clock() : 0;
cout << "Bubble:\n";
printArrayTime(arrBuble, (end_time-start_time)/CLK_TCK);
start_time = clock() != -1 ? clock() : 0;
QuickSort(arrQuick, 0, SIZE);
end_time = clock() != -1 ? clock() : 0;
cout << "Quick:\n";
printArrayTime(arrQuick, (end_time - start_time) / CLK_TCK);
cout << "Time" << "\n" << (clock() - k) / CLK_TCK << "\n";
return 0;
}
/
Висновок: на цій лабораторній, я навчився складати програму, яка порівнює два алгоритми за характеристикою часової складності.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора