Програмування та відлагодження алгоритму внутрішнього сортування методом злиття

Тема: програмування та відлагодження алгоритму внутрішнього сортування методом злиття. Визначення складності алгоритму та часу його виконання.

Мета: проаналізувати та дослідити алгоритм сортування шляхом злиття.

Хід роботи:

Ідея сортування методом злиття полягає у тому, щоб розділити набір елементів, який необхідно відсортувати, на дві частини, потім відсортувати кожну з цих частин і злити їх у відсортований набір.

Кроки сортування методом злиття наступні:

1.Розбити набір елементів на дві рівні частини.

2.Рекурсивно відсортувати кожну з цих частин, використовуючи той самий алгоритм сортування.

3.Злити відсортовані частини в один відсортований набір, порівнюючи елементи з кожної частини і розміщуючи їх в правильному порядку.

4.Повторювати кроки 1-3, поки не буде відсортований весь набір елементів.

Сортування методом злиття є ефективним алгоритмом сортування, який має складність O(n log n), де n - кількість елементів, які необхідно відсортувати. Це робить його одним з найшвидших алгоритмів сортування для великих наборів даних.

Основна ідея цього алгоритму полягає у тому, що сортування відбувається під час злиття двох відсортованих підмасивів, тому час сортування залежить від часу злиття. Алгоритм гарантує сортування за O(n log n) часу, де n - кількість елементів у масиві, що сортується

Виконання сортування злиттям на масиві[4, 0, 6, 2, 5, 1, 7, 3]

Код сортування:

#include <iostream>

using namespace std;

void merge(int arr[], int p, int q, int r) {

int n1 = q - p + 1;

int n2 = r - q;

int L[n1], M[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[p + i];

for (int j = 0; j < n2; j++)

M[j] = arr[q + 1 + j];

int i, j, k;

i = 0;

j = 0;

k = p;

while (i < n1 && j < n2) {

if (L[i] <= M[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = M[j];

j++;

}

k++;

}

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

while (j < n2) {

arr[k] = M[j];

j++;

k++;

}

}

void mergeSort(int arr[], int l, int r) {

if (l < r) {

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

}

}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)

cout << arr[i] << " ";

cout << endl;

}

int main() {

int arr[] = {45, 23, 12, 10, 9, 6, 34, 76, 21, 4};

int size = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, size - 1);

cout << "Sorted array: \n";

printArray(arr, size);

return 0;

}

Виконання коду:

Алгоритм сортування злиттям (merge sort) має загальну теоретичну складність O(n log n), де n - кількість елементів, які потрібно відсортувати. Але залежно від вхідних даних, складність може відрізнятися.

Найкращий випадок - відсортований масив

У найкращому випадку, коли вхідний масив вже відсортований, складність алгоритму складається