મર્જ કરો સortર્ટ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બૂમરેંગ કોમર્સ ગોલ્ડમૅન સૅશ ગ્રૂફર્સ માઈક્રોસોફ્ટ ઓરેકલ પેટીએમ ક્યુઅલકોમ સ્નેપડીલ ટાર્ગેટ કોર્પોરેશન
વિભાજીત અને વિજય સોર્ટિંગ

મર્જ સ sortર્ટ શું છે?

મર્જ કરો સortર્ટ છે એક પુનરાવર્તિત કાર્યવાહી. તે પણ એ વિભાજીત અને જીતી અલ્ગોરિધમનો. હવે આપણે એ જાણવાની જરૂર છે કે ભાગ અને અલ્ગોરિધમનો વિજય શું છે? તે એક પ્રકારની પ્રક્રિયા છે જેમાં આપણે સમસ્યાને પેટાપ્રbleબ્લમ્સમાં વહેંચીએ છીએ અને જ્યાં સુધી અમને ટૂંકમાં હલ થયેલ સબપ્રbleબ્લેમ ન મળે ત્યાં સુધી તેને વહેંચીએ છીએ. ટૂંકા ઉકેલાયેલા સબપ્રોબ્લેમ મર્જ કરીને આપણે મોટી / મુખ્ય સમસ્યાનું સમાધાન શોધી શકીએ છીએ. ચાલો જોઈએ અલ્ગોરિધમનો મર્જર_સortર્ટ માટે.

અલ્ગોરિધમ

પગલું 1 સમસ્યાને 2 પેટા સમસ્યાઓમાં તોડો.

પગલું 2 સબ પ્રોબ્લેમ્સ ઓછામાં ઓછા કદ સુધી પહોંચે ત્યાં સુધી પુનરાવર્તિત ક callલ કરે છે (ઉકેલાયેલી સબપ્રોબ્લેમ).

પગલું 3 ઉકેલાયેલી સબપ્રbleબ્લેમ્સને મર્જ કરો.

હવે, ઉદાહરણ માટે ખસેડો સમજવું કે આ અલ્ગોરિધમનો કેવી રીતે કાર્ય કરે છે?

માટે સમજૂતી મર્જ કરો સortર્ટ

ચાલો લઈએ કે આપણી પાસે એક એરે છે જેમાં એન નંબરવાળી સ unsર્ટમાં છે. એ = {9,1,4,2,5,3,7,2,6,17}

મર્જ કરો સortર્ટ

મર્જ કરો સortર્ટ

મર્જ કરો સortર્ટ

મર્જ કરો સortર્ટ

મર્જ કરો સortર્ટ

મર્જ કરો સortર્ટ

પગલું 8 માં અમને ફાઇનલ મળ્યું સortedર્ટ કરેલ એરે મર્જર_સોર્ટ અલ્ગોરિધમનો ઉપયોગ કરીને.

મર્જ સortર્ટ માટે અમલીકરણ 

/*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

સમયની જટિલતા

ઓ (એન * લ Nગ એન) જ્યાં એન એરેમાં કુલ સંખ્યા છે. ઉપરોક્ત અમલીકરણનો પુનરાવર્તન સંબંધ છે ટી (એન) = 2 * ટી (એન / 2) + ઓ (1).

અવકાશ જટિલતા

ઓ (1) અહીં આપણે આપેલ એરે સિવાય કોઈ વધારાનું સ્થાન બનાવ્યું નથી, તેથી જગ્યા જટિલતા ઓ (1) છે જે સતત છે.

વપરાયેલ અલ્ગોરિધમનો પ્રકાર

મર્જ સ sortર્ટને હલ કરવા માટે આપણે અહીં વિભાજન અને વિજયનો અભિગમનો ઉપયોગ કરીએ છીએ.

સંદર્ભ