دمج الفرز


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل تجارة بوميرانج جولدمان ساكس Grofers Microsoft أوراكل Paytm كوالكوم Snapdeal شركة الهدف
فرق تسد فرز

ما هو نوع الدمج؟

دمج الفرز هو إجراء تكراري. بل هو أيضا فرق ينتصر الخوارزمية. الآن نحن بحاجة لمعرفة ما هي خوارزمية فرق تسد؟ إنه نوع من الإجراءات نقسم فيه المشكلة إلى مشكلات فرعية ونقسمها حتى نجد أقصر مشكلة فرعية تم حلها. من خلال دمج أقصر مشكلة فرعية تم حلها ، نجد الحل للمشكلة الكبيرة / الرئيسية. دعونا نرى خوارزمية من أجل merge_sort.

خوارزمية

الخطوة: 1 قسّم المشكلة إلى مشكلتين فرعيتين.

الخطوة: 2 استدعاء المشاكل الفرعية بشكل متكرر حتى تصل إلى الحد الأدنى للحجم (مشكلة فرعية محلولة).

الخطوة: 3 دمج المشاكل الفرعية التي تم حلها.

الآن ، انتقل إلى مثال فهم كيف تعمل هذه الخوارزمية؟

شرح ل دمج الفرز

لنأخذ لدينا مصفوفة A تحتوي على عدد N غير مصنف. أ = {9,1,4,2,5,3,7,2,6,17،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

دمج الفرز

دمج الفرز

دمج الفرز

دمج الفرز

دمج الفرز

دمج الفرز

في الخطوة 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).

تعقيد الفضاء

يا (1) هنا لم نخلق أي مساحة إضافية باستثناء مجموعة معينة ، لذا فإن تعقيد الفضاء هو O (1) وهو ثابت.

نوع الخوارزمية المستخدمة

هنا نستخدم طريقة فرق تسد لحل فرز الدمج.

مراجع