Порівняльний аналіз ефективності алгоритмів сортування
Автор: Сергей Тресков • Ноябрь 16, 2022 • Лабораторная работа • 1,885 Слов (8 Страниц) • 118 Просмотры
Міністерство освіти і науки України Харківський національний університет радіоелектроніки
Кафедра системотехніки
Дисципліна: Теорія алгоритмів
Лабораторна робота на тему:
«Порівняльний аналіз ефективності алгоритмів сортування»
Виконав Перевірив
студент групи КНТ-21-3 асис. Панкратова Ю. Э
Тресков Сергій Павлович Оцінка « » 2021 р.
Харків 2021
- Мета заняття
Вивчення алгоритмів сортування масивів, порівняння їх за швидкодією
і витратам пам'яті, вдосконалення практичних навичок роботи з масивами і
функціями.
- Хід роботи
[pic 1]
Короткий опис алгоритмів:
Selection:
- Починаючи з елемента під індексом 0, шукаємо в масиві найменше значення.
- Знайдене значення міняємо місцями з нульовим елементом.
- Повторюємо кроки №1 і №2 вже для наступного індексу в масиві (відсортований елемент більше не чіпаємо).
Merge Sort:
- Якщо в розглянутому масиві один елемент, то він вже відсортований-алгоритм завершує роботу.
- Інакше масив розбивається на дві частини, які сортуються рекурсивно.
- Після сортування двох частин масиву до них застосовується процедура злиття, яка за двома відсортованими частинами отримує вихідний відсортований масив.
Heap Sort:
- Побудуйте max-heap з вхідних даних.
- На даному етапі найбільший елемент зберігається в корені купи. Замініть його на останній елемент купи, а потім зменшіть його розмір на 1. Перетворіть отримане дерево в max-heap з новим коренем.
- Повторювати вищевказані кроки, поки розмір купи більше 1.
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
void FillArry(int* arry1, int* arry2, int* arry3, int size) {
int a;
random_device rd;
mt19937 mersenne(rd());
for (int i{}; i < size; i++) {
a = mersenne() % 65535;
arry1[i] = a;
arry2[i] = a;
arry3[i] = a;
}
}
void PrintArry(int* arry, int size) {
for (int i{}; i < size; i++) {
cout << arry[i] << " ";
}
cout << endl;
}
void SelectionSort(int* arry1, int size) {
for (int i = 0; i < size - 1; ++i)
{
int min_indx = i;
for (int j = i + 1; j < size; ++j)
{
if (arry1[j] < arry1[min_indx])
min_indx = j;
}
swap(arry1[i], arry1[min_indx]);
}
}
void Merge(int A[], int p, int q, int r)
{
int n1, n2, i, j, k;
n1 = q - p + 1;
n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for (i = 0; i < n1; i++)
{
L[i] = A[p + i];
}
for (j = 0; j < n2; j++)
{
R[j] = A[q + j + 1];
}
i = 0, j = 0;
for (k = p; i < n1 && j < n2; k++)
{
if (L[i] < R[j])
{
A[k] = L[i++];
}
else
{
A[k] = R[j++];
}
}
while (i < n1)
{
A[k++] = L[i++];
}
while (j < n2)
{
A[k++] = R[j++];
}
delete[] L;
delete[] R;
}
void MergeSort(int A[], int p, int size) {
...