Эрэмбэлэх  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Бумерангын худалдаа Goldman Sachs Горхи Microsoft- Oracle-ийн Paytm Qualcomm Snapdeal Зорилтот корпораци
Хуваагаад, ялж байна Ангилах

Merge sort гэж юу вэ?  

Эрэмбэлэх нь Рекурсив журамБайна. Энэ нь мөн a хувааж, байлдан дагуул алгоритм. Одоо алгоритм хувааж, байлдан дагуулах гэж юу болохыг мэдэх хэрэгтэй байна уу? Энэ бол асуудлыг дэд асуудалд хувааж, хамгийн богино шийдэгдсэн дэд асуудлыг олох хүртэл хуваах процедурын төрөл юм. Хамгийн богино хугацаанд шийдэгдсэн дэд асуудлыг нэгтгэснээр бид том / гол асуудлын шийдлийг олох болно. -Г үзье алгоритм нэгтгэхийн тулд.

Алгоритм  

1-р алхам Асуудлыг 2 дэд асуудал болгон хуваа.

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 * log N) энд N нь массив дахь нийт тоо юм. Дээрх хэрэгжилтийн давтагдах хамаарал нь T (N) = 2 * T (N / 2) + O (1).

мөн үзнэ үү
Тодорхой элемент бүхий дэд зурвасууд

Сансрын нарийн төвөгтэй байдал  

O (1) Энд бид өгөгдсөн массиваас өөр ямар ч нэмэлт зай үүсгээгүй тул орон зайн нарийн төвөгтэй байдал нь тогтмол O (1) болно.

Ашигласан алгоритмын төрөл  

Энд бид нэгтгэх төрлийг шийдэхийн тулд хуваах, байлдан дагуулах аргыг ашигладаг.

Ашигласан материал