Сұрыптауды біріктіру


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма Бумеранг коммерциясы Голдман Сакс Грейфтерлер Microsoft Oracle Paytm Qualcomm Шапшаң Target Corporation
Бөліңіз және жеңіңіз Сұрыптау

Біріктіруді сұрыптау дегеніміз не?

Сұрыптауды біріктіру Бұл Рекурсивті процедура. Бұл да а бөлу және жеңу алгоритм. Алгоритмді бөлу және бағындыру дегеніміз не? Бұл біз есепті ішкі проблемаларға бөліп, ең қысқа шешілген ішкі проблеманы тапқанға дейін бөлетін процедураның түрі. Ең қысқа шешілген ішкі проблеманы біріктіру арқылы біз үлкен / негізгі проблеманың шешімін табамыз. Келіңіздер, көрейік алгоритм біріктіру_сұрыптау үшін.

Алгоритм

Қадам: 1 Мәселені екі ішкі проблемаға бөліңіз.

Қадам: 2 Кіші проблемалар рекурсивті түрде минималды өлшемге жеткенше шақырылады (шешілген ішкі проблема).

Қадам: 3 Шешілген ішкі проблемаларды біріктіріңіз.

Енді мысалға көшіңіз осы алгоритмнің қалай жұмыс істейтінін түсіну?

Түсініктеме Сұрыптауды біріктіру

Бізде сұрыпталмаған N саны бар А массиві бар. A = {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) болады.

Қолданылатын алгоритм түрі

Мұнда біз біріктіру сұрыптауын шешу үшін бөлу және жеңу тәсілін қолданамыз.

Әдебиеттер тізімі