Порівняльний аналіз ефективності алгоритмів сортування
Автор: Ярослав Мірошніченко • Декабрь 17, 2021 • Лабораторная работа • 1,237 Слов (5 Страниц) • 182 Просмотры
Міністерство освіти і науки України
Харківський національний університет радіоелектроніки
Кафедра системотехніки
Дисципліна: Теорія алгоритмів
Лабораторна робота № 3. Порівняльний аналіз ефективності алгоритмів сортування.
Виконав Перевірив
студент групи КНТ-21-6 к.т.н.,ст.викладач каф.СТ
Мірошніченко Ярослав Сергійович Морозова А.І.
Оцінка ____________
«____»__________2021р.
Харків 2021
3.1 Мета роботи:
Вивчення алгоритмів сортування масивів, порівняння їх за швидкодією і витратам пам'яті, вдосконалення практичних навичок роботи з масивами і функціями.
3.2 Хід роботи
Варіант 19
Опис трьох методів сортування:
InsertionSort (Сортування вставкою) — це простий алгоритм сортування. Масив практично розбивається на відсортовану та несортовану частини. Значення з несортованої частини вибираються і розміщуються в правильній позиції в відсортованій частині.
MergeSort (Сортування злиттям) - алгоритм сортування масиву, який реалізований за принципом "розділяй і владарюй". Завдання сортування масиву розбивається на кілька підзадач сортування масивів меншого розміру, після виконання яких результат комбінується, що і призводить до вирішення початкової задачі.
ShellSort в основному є різновидом сортування вставкою. У сортуванні вставкою ми переміщуємо елементи лише на одну позицію вперед. Коли елемент потрібно перемістити далеко вперед, задіяно багато рухів. Ідея ShellSort полягає в тому, щоб дозволити обмін далекими елементами.
3.3 Код програми:
#include <iostream>
#include <time.h>
using namespace std;
void fill_of_arr(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = rand() % 65535;
}
}
void print_of_arr(int arr[], int size)
{
std::cout << endl;
for (int i = 0; i < size; i++)
{
std::cout << arr[i] << "\t";
}
std::cout << endl;
}
void InsertionSort(int arr[], int size) {
int i, key, j;
for (i = 1; i < size; i++) {
key = arr[i];
j = i
- 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j
- 1;
}
arr[j + 1] = key;
}
}
void Heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
Heapify(arr, n, largest);
}
}
void MergeSort(int d_arr[], int size) {
for (int i = size / 2
...