मर्ज़ सॉर्ट


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब बूमरैंग कॉमर्स गोल्डमैन सैक्स Grofers माइक्रोसॉफ्ट ओरेकल Paytm क्वालकॉम स्नैपडील टारगेट निगम
विभाजन और जीत छंटाई

मर्ज सॉर्ट क्या है?

मर्ज़ सॉर्ट एक पुनरावर्ती प्रक्रिया। यह भी ए फूट डालो और जीतो कलन विधि। अब हमें यह जानने की जरूरत है कि एल्गोरिथ्म क्या है? यह एक प्रकार की प्रक्रिया है जिसमें हम समस्या को उप-उपखंडों में विभाजित करते हैं और उन्हें तब तक विभाजित करते हैं जब तक कि हम सबसे कम हल की हुई उप-उपाधि न पा लें। सबसे छोटी हल की हुई उपप्रकार को विलीन करके हम बड़ी / मुख्य समस्या का हल ढूंढते हैं। आइए देखते हैं कलन विधि merge_sort के लिए।

कलन विधि

चरण 1 समस्या को 2 उपप्रकारों में तोड़ें।

चरण 2 जब तक वे न्यूनतम आकार (हल किए गए उपप्रोब्लेम) तक नहीं पहुंचते, तब तक उपप्रकारक पुनरावर्ती कॉल करते हैं।

चरण 3 हल किए गए उपप्रोग्राम को मर्ज करें।

अब, उदाहरण के लिए आगे बढ़ते हैं समझने के लिए कि यह एल्गोरिथ्म कैसे काम करता है?

के लिए स्पष्टीकरण मर्ज़ सॉर्ट

आइए हम एक सरणी लेते हैं जिसमें A एक एन नंबर होता है। A = {9,1,4,2,5,3,7,2,6,17}

मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

मर्ज़ सॉर्ट

चरण 8 में हमें फाइनल मिला क्रमबद्ध सरणी मर्ज_सॉर्ट एल्गोरिथम का उपयोग करना।

मर्ज सॉर्ट के लिए कार्यान्वयन 

/*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 * log N) जहाँ N एक सरणी में मौजूद कुल संख्या है। उपरोक्त कार्यान्वयन का पुनरावृत्ति संबंध है T (N) = 2 * T (N / 2) + O (1).

अंतरिक्ष जटिलता

ओ (1) यहाँ हमने दिए गए सरणी को छोड़कर कोई अतिरिक्त स्थान नहीं बनाया, इसलिए अंतरिक्ष जटिलता O (1) है जो निरंतर है।

उपयोग किए गए एल्गोरिदम का प्रकार

यहां हम मर्ज को हल करने के लिए डिवाइड और विजय दृष्टिकोण का उपयोग करते हैं।

संदर्भ