15
Реалізація
static void merge(int a[], int Firstindex, int m, int Lastindex, bool direct); static void __mergeSort(int a[], int Firstindex, int Lastindex, bool direct)
{
if (Firstindex < Lastindex)
{
int m = Firstindex + (Lastindex - Firstindex)/2;
__mergeSort(a, Firstindex, m, direct); __mergeSort(a, m+1, Lastindex, direct);
merge(a, Firstindex, m, Lastindex, direct);
}
}
static void merge(int a[], int Firstindex, int m, int Lastindex, bool direct)
{
int x; int y; int z;
int sub1 = m - Firstindex + 1; int sub2 = Lastindex - m;
int First[sub1]; //temp array
int Second[sub2];
for (x = 0; x < sub1; x++) // copying data to temp arrays First[x] = a[Firstindex + x];
for (y = 0; y < sub2; y++) Second[y] = a[m + 1+ y];
x = 0; y = 0;
z = Firstindex;
while (x < sub1 && y < sub2)
{
if(direct)
{
if (First[x] <= Second[y])
{
a[z] = First[x]; x++;
}
16
else
{
a[z] = Second[y]; y++;
}
} else
{
if (First[x] >= Second[y])
{
a[z] = First[x]; x++;
}
else
{
a[z] = Second[y]; y++;
}
}
z++;
}
while (x < sub1)
{
a[z] = First[x]; x++;
z++;
}
while (y < sub2)
{
a[z] = Second[y]; y++;
z++;
}
}
17
2.7 Алгоритм пірамідального сортування (Heap sort)
Основна ідея - шукаємо максимальний елемент в невідсортованій частині масиву і ставимо його в кінець подмассіва. У пошуках максимуму підмасив перебудовується в так зване Сортувальне дерево (вона ж бінарна купа, вона ж піраміда), в результаті чого максимум сам "спливає" в початок масиву. Після цього переміщуємо максимум в кінець пыдмасива. Потім над частиною масиву , що залишилася знову здійснюється процедура перебудови в сортувальне дерево з подальшим переміщенням максимуму в кінець підмасива.
Сортувальне дерево - дерево у якого будь-який батько не менше ніж кожен з його нащадків. Якщо Сортувальне дерево незростаюча, то, відповідно, будь-який батько не більше ніж кожен з його нащадків.
Аналіз пірамідального сортування
Ми можемо стверджувати, що основна операція з купою Heapify виконується за
O(log(n)) часу, тому що купа має |
O(log(n)) |
рівні, і просіяний елемент |
рухається вниз на один рівень дерева після постійного обсягу роботи. |
||
Виходячи з цього, ми можемо зрозуміти що: |
|
|
1. Що для побудови купи потрібно |
O(n log(n)) |
часу , оскільки нам потрібно |
застосувати Heapify приблизно n / 2 рази (до кожного з внутрішніх вузлів), і (2) що потрібно ч асу на вилучення кожного з максимальних елементів, оскільки нам потрібно витягти приблизно n елементів, і кожне вилучення передбачає постійний обсяг роботи та один Heapify. Тому загальний час роботи пірамідального сортування дорівнює .
18
Реалізація
static void swap(int* a, int* b)
{
int t = *a; *a = *b; *b = t;
}
static void heapify(int arr[], int n, int root, bool direction)
{
int largest = root; // root is the largest element int l = 2*root + 1; // left
int r = 2*root + 2; // right
if(!direction)
{
if (l < n && arr[l] < arr[largest]) largest = l;
if (r < n && arr[r] < arr[largest]) largest = r;
}
else
{
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
}
if (largest != root)
{
swap(&arr[root], &arr[largest]);
heapify(arr, n, largest, direction);
}
}
void heap_sort(int arr[], int n, bool direction)
{
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i, direction);
for (int i=n-1; i>=0; i--)
19
{
swap(&arr[0], &arr[i]);
heapify(arr, i, 0, direction);
}
}
Методологія тестування
1. Апаратне забезпечення Тестування проводилося на такому апаратному забезпеченні:
•Ryzen 5 2500U(2 — 3.6 Ghz)
•8Gb RAM (6.74Gb available)
2.Програмне забезпечення
Тестування проводилося на такому програмному забезпеченні:
•OС - GNU/Linux x86_64
•Дистрибутив - Manjaro Linux
•Версія ядра - 5.9.11
•IDE — Clion
•Компілятор — Clang
3.Тестові дані
Тестові дані представляють собою одновимірні масиви чисел типу int.
•(Тест 0) Випадково згенеровані дані
•(Тест 1) Відсортовані у зворотньому порядку дані
•(Тест 2) Частково (на половину) відсортовані дані
•(Тест 3) Відсортовані дані Розмірність даних являє собою :
•10
•100
•1000
•10000
•100000
Для першої групи сортувань, і :
•10
•100
•1000
•10000
•100000
•1000000
Для другої групи сортувань