Аб'яднаць сартаванне


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Камерцыя "Бумеранг" Goldman Sachs Граферс Microsoft Аракул Paytm Qualcomm Snapdeal Target Corporation
Падзялі і перамагай сартаванне

Што такое сартаванне зліцця?

Аб'яднаць сартаванне з'яўляецца Рэкурсіўная працэдура. Гэта таксама падзяліць і заваяваць алгарытм. Цяпер нам трэба ведаць, што такое алгарытм падзяліць і заваяваць? Гэта тып працэдуры, пры якой мы дзелім задачу на падзадачы і дзелім іх, пакуль не знойдзем самую кароткую развязаную падзадачу. Аб'яднаўшы самую кароткую развязаную падзадачу, мы знаходзім рашэнне вялікай / галоўнай праблемы. Давайце паглядзім алгарытм для зліцця_сартавання.

Алгарытм

Крок 1 Разбіце праблему на 2 падзадачы.

Крок 2 Падзадачы выклікаюцца рэкурсіўна, пакуль яны не дасягнуць мінімальнага памеру (вырашана падзадача).

Крок 3 Аб'яднаць вырашаныя падзадачы.

Зараз пераходзім да прыкладу для разуменне таго, як працуе гэты алгарытм?

Тлумачэнне для Аб'яднаць сартаванне

Давайце возьмем масіў A, які змяшчае N-нумар у сартаванні. А = {9,1,4,2,5,3,7,2,6,17}

Аб'яднаць сартаванне

Аб'яднаць сартаванне

Аб'яднаць сартаванне

Аб'яднаць сартаванне

Аб'яднаць сартаванне

Аб'яднаць сартаванне

На этапе 8 мы атрымалі фінал адсартаваны масіў з выкарыстаннем алгарытму merge_sort.

Рэалізацыя для сартавання зліцця 

/*C++ Implementation of Merge Sort*/ 
#include<bits/stdc++.h>
#define max_v 100000
using namespace std;
void add_subproblems(int a[],int l,int mid,int r)
{
    int start_1=l;//starting index of subproblem 1;
    int start_2=mid+1;//strating index of subproblem 2;
    int store=l;//used to store the no in array a with O(1) space complexity. 
    /*compare the element from begining of both subproblems and choose the minimum element from them
      and increment the index wrt minimum value by 1.*/
    while(start_1<=mid&&start_2<=r)
    {
        if((a[start_1]%max_v)<=(a[start_2]%max_v))
        {
            a[store]+=(a[start_1]%max_v)*max_v;
            store++;
            start_1++;
        }
        else
        {
            a[store]+=(a[start_2]%max_v)*max_v;
            store++;
            start_2++;
        }
    }
    /*if some elements are remaining in subproblem 1*/
    while(start_1<=mid)
    {
        a[store]+=(a[start_1]%max_v)*max_v;
        store++;
        start_1++; 
    }
    /*if some elements are remaining in subproblem 2*/
    while(start_2<=r)
    {
        a[store]+=(a[start_2]%max_v)*max_v;
        store++;
        start_2++;
    }
    /*now change the elements into their oroginal values*/
    for(int i=l;i<=r;i++)
    {
        a[i]/=max_v;
    }
}
void merge(int a[],int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merge(a,l,mid);
        merge(a,mid+1,r);
        add_subproblems(a,l,mid,r);
    }
}
int main() 
{ 
    int number;
    /*total numbers which we want to sort*/
    cin>>number;
    int a[number];
    /*take input*/
    for(int i=0;i<number;i++)
    {
        cin>>a[i];
    }
    cout<<"Array before sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    /*call merge function*/
    merge(a,0,number-1);
    cout<<"Array after sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    return 0; 
}
10
9 1 4 2 5 3 7 2 6 17
Array before sorting: 9 1 4 2 5 3 7 2 6 17 
Array after sorting: 1 2 2 3 4 5 6 7 9 17

Часовая складанасць

O (N * часопіс N) дзе N - агульная колькасць масіва. Суадносіны паўтарэння вышэйзгаданай рэалізацыі ёсць T (N) = 2 * T (N / 2) + O (1).

Касмічная складанасць

O (1) тут мы не стварылі дадатковай прасторы, акрамя дадзенага масіва, таму складанасць прасторы роўная O (1), якая з'яўляецца пастаяннай.

Тып выкарыстоўванага алгарытму

Тут мы выкарыстоўваем падыход падзяліць і перамагчы, каб вырашыць сартаванне зліцця.

Спасылкі