Միավորել Տեսակավորումը  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon խնձոր Բումերանգի առևտուր Goldman Sachs-ը Grofers Microsoft Պատգամախոս Paytm Qualcomm Snapdeal Target Corporation- ը
Բաժանել եւ նվաճել դասավորում

Ի՞նչ է միաձուլման տեսակավորումը:  

Միավորել Տեսակավորումը է Ռեկուրսիվ ընթացակարգ. Այն նաև ա բաժանել ու նվաճել ալգորիթմ Այժմ մենք պետք է իմանանք, թե ինչ է բաժանման և հաղթելու ալգորիթմը: Դա ընթացակարգի մի տեսակ է, որի ընթացքում մենք խնդիրը բաժանում ենք ենթախնդիրների և բաժանում դրանք մինչև գտնենք ամենակարճ լուծված ենթածրագիրը: Միաձուլելով ամենակարճ լուծված ենթածրագիրը `մենք գտնում ենք մեծ / հիմնական խնդրի լուծումը: Եկեք տեսնենք ալգորիթմ merge_sort- ի համար:

Ալգորիթմ  

Քայլ ՝ 1 Խնդիրը բաժանեք 2 ենթախնդրի:

Քայլ ՝ 2 Ենթախնդիրները զանգահարում են ռեկուրսիվ, մինչև հասնեն նվազագույն չափի (լուծված ենթախնդիր):

Քայլ ՝ 3 Միաձուլեք լուծված ենթածրագրերը:

Այժմ անցեք օրինակին հասկանալով, թե ինչպես է աշխատում այս ալգորիթմը:

Բացատրություն համար Միավորել Տեսակավորումը  

Եկեք վերցնենք, որ մենք ունենք A զանգված, որը պարունակում է N թիվ, չհավաքված: A = {9,1,4,2,5,3,7,2,6,17}

Միավորել ՏեսակավորումըPin

Միավորել ՏեսակավորումըPin

Միավորել ՏեսակավորումըPin

Միավորել ՏեսակավորումըPin

Միավորել ՏեսակավորումըPin

Pin

Միավորել ՏեսակավորումըPin

Pin

Քայլ 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

Timeամանակի բարդությունը  

O (N * տեղեկամատյան N) որտեղ N - զանգվածում առկա ընդհանուր թիվն է: Վերոհիշյալ իրականացման կրկնության հարաբերությունն է T (N) = 2 * T (N / 2) + O (1).

Տես նաեւ,
Ենթածրագրեր `հստակ տարրերով

Տիեզերական բարդություն  

Ո (1) այստեղ մենք ոչ մի լրացուցիչ տարածք չենք ստեղծել, բացի տրված զանգվածից, այնպես որ տարածության բարդությունը O (1) է, որը հաստատուն է:

Օգտագործված ալգորիթմի տեսակը  

Այստեղ մենք օգտագործում ենք բաժանման և հաղթելու մոտեցումը `լուծելու միաձուլումը:

Սայլակ