מיזוג מיון


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ מסחר בומרנג גולדמן זאקס מגדלים מיקרוסופט אורקל Paytm קוואלקום Snapdeal תאגיד היעד
הפרד ומשול מִיוּן

מהו מיון מיזוג?

מיזוג מיון הוא נוהל רקורסיבי. זה גם א מתחלקים וכובשים אַלגוֹרִיתְם. כעת עלינו לדעת מהו אלגוריתם חלוקה וכיבוש? זהו סוג של פרוצדורה בה אנו מחלקים את הבעיה לבעיות משנה ומחלקים אותם עד שנמצא את בעיית המשנה הקצרה ביותר שנפתרה. על ידי מיזוג בעיית המשנה שנפתרה בקצרה אנו מוצאים את הפיתרון לבעיה הגדולה / העיקרית. בוא נראה את אַלגוֹרִיתְם למיזוג_סורט.

אַלגוֹרִיתְם

שלב 1 פרקו את הבעיה לשתי בעיות משנה.

שלב 2 בעיות משנה מתקשרות רקורסיבית עד שהן מגיעות לגודל מינימלי (בעיית משנה נפתרת).

שלב 3 למזג את בעיות המשנה שנפתרו.

כעת, עבור לדוגמא עבור להבין כיצד אלגוריתם זה עובד?

הסבר ל מיזוג מיון

בואו ניקח שיש לנו מערך A המכיל מספר 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 * log N) כאשר N הוא המספר הכולל הקיים במערך. יחס ההישנות של היישום הנ"ל הוא T (N) = 2 * T (N / 2) + O (1).

מורכבות בחלל

O (1) כאן לא יצרנו שום מרחב נוסף למעט מערך נתון ולכן, מורכבות החלל היא O (1) שהיא קבועה.

סוג האלגוריתם בשימוש

כאן אנו משתמשים בגישת החלוקה והכיבוש כדי לפתור מיון מיזוג.

הפניות