Алгоритм сортування масиву методом злиття

Міністерство освіти та науки України

Вінницький національний технічний університет

Факультет інформаційних технологій та комп'ютерної інженерії

Кафедра комп'ютерних наук

Лабораторна робота №3

Виконав студент групи 2КН-19Б:

Любчич Н.О.

Перевірив:

Арсенюк І.Р

Вінниця-2019

Тема: “Алгоритм сортування масиву методом злиття”.

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

Ідея:  Вихідна задача розбивається на декілька підзадач меншого розміру. Ці підзадачі розв’язуються за  допомогою рекурсивного виклику або безпосередньо, якщо їх розмір досить малий.  Розв’язки цих підзадач комбінуються і ми отримуємо шуканий розв’язок вихідної задачі.

Хід роботи: Розбиваємо вихідний масив на 2 половини меншого розміру. Сортуємо кожну з цих половин окремо. З’єднуємо 2 впорядкованих масиви половинного розміру в один.

Схема алгоритму:[pic 1]

MergeSort(int[] array)

       if array.Length == 1 do

           return array;

       middle_point = array.Length / 2;

       return Merge(MergeSort(array.Take(middle_point).ToArray()), MergeSort(array.Skip(middle_point).ToArray()));

Merge(int[] array_Left, int[] array_Right)

       a = 0, b = 0;

       merged = new int[array_Left.Length + array_Right.Length];

       for i = 0 i to array_Left.Length + array_Right.Length do

           if b < array_Right.Length && a < array_Left.Length then

               if array_Left[a] > array_Right[b] && b < array_Right.Length

                    then merged[i] = array_Right[b++];

               else

                    merged[i] = array_Left[a++];

           else

               if b < array_Right.Length then

                    merged[i] = array_Right[b++];

               else

                    merged[i] = array_Left[a++];

       for end    

       return merged;

Аналіз складності алгоритму:

T(n) = a*T(n/b) + O(n)

Оскільки ми розбиваємо алгоритм на 2, то a = 2; b = 2;

T(n) = 2*T(n/2) + O(n)

Якщо довжина масиву n = 1, то T(1) = O(1). Отже T(n) = O(n*log(n))

Реалізація алгоритму сортування на мові програмування C#:

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace MergeSort

{

    class Program

    {

        public static int[] MergeSort(int[] array)

        {

            if (array.Length == 1)

                return array;

            int middle_point = array.Length / 2;

            return Merge(MergeSort(array.Take(middle_point).ToArray()), MergeSort(array.Skip(middle_point).ToArray()));

        }

        public static int[] Merge(int[] array_Left, int[] array_Right)

        {

            int a = 0, b = 0;

            int[] merged = new int[array_Left.Length + array_Right.Length];

            for (int i = 0; i < array_Left.Length + array_Right.Length; i++)

            {

                if (b < array_Right.Length && a < array_Left.Length)

                    if (array_Left[a] > array_Right[b] && b < array_Right.Length)

                        merged[i] = array_Right[b++];

                    else

                        merged[i] = array_Left[a++];

                else

                    if (b < array_Right.Length)

                    merged[i] = array_Right[b++];

                else

                    merged[i] = array_Left[a++];

            }

            return merged;