ترتيب ڏيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ايپل بوميرنگ ڪامرس Goldman سيچ گرافس Microsoft جي Oracle پيٽرم Qualcomm اسپيڊل ھدايتون ڪارپوريشن
تقسيم ۽ فتح ترتيب ڏيڻ

ضم ٿيل قسم ڇا آهي؟

ترتيب ڏيو هڪ آهي ڪاروائي جو طريقو. اهو پڻ هڪ آهي ورهايو ۽ فتح ڪريو الگورتھم. هاڻي اسان کي toاڻڻ گهرجي ته الگورٿيم ڪي تقسيم ۽ فتح ڪريو؟ اهو هڪ قسم جو طريقيڪار آهي جنهن ۾ اسين مسئلي کي ذيلي مسئلن ۾ ورهايو ۽ ورهايو جيستائين اسان نن solvedا حل وارا سبيل مسئلو ڳوليون. مختصر حل ٿيل سبجيم کي ضم ڪرڻ سان اسان وڏي / بنيادي مسئلي جو حل ڳوليندا آهيون. اچو ته ڏسو الخوارزمي ضم ڪرڻ جي لاءِ

الورورٿم

قدم: 1 مسئلو کي 2 ذيلي مضمونن ۾ ٽوڙيو.

قدم: 2 ذيلي مسئلا وقتي طور تي ڪال ڪندا آهن جيستائين اهي گهٽ کان گهٽ سائيز تائين نه پهچي وڃن (حل ٿيل سبيلبل).

قدم: 3 حل ٿيل ذيلي مضمونن کي گڏ ڪريو.

ھاڻي ، مثال ڏانھن وڃو سمجھڻ جو اھو الگورتھم ڪيئن ڪم ڪري ٿو؟

جي وضاحت ترتيب ڏيو

اچو ته اسان وٽ هڪ ترتيب ڏنل آهي اي نمبر جنهن ۾ ن نمبر نه ٿيل آهي. الف = {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

وقت جي پيچيدگي

اي (اين * لاگ اين) جتي اين ھڪڙي صف ۾ موجود تعداد آھي. مٿين عمل درآمد جو ٻيهر تڪرار هوندو آهي ٽي (اين) = 2 * ٽي (اين / 2) + اي (1).

خلائي پيچيدگي

اي (1) هتي اسان ڏنل جڳهه کانسواءِ ڪابه اضافي جڳهه پيدا نه ڪئي آهي ، خلائي پيچيدگي او (1) آهي جيڪا مستقل آهي.

الگورتھم جو قسم استعمال ڪيو ويو

هتي اسان ضم ٿيل قسم کي حل ڪرڻ لاءِ تقسيم ۽ فتح واري طريقي کي استعمال ڪريون ٿا.

حوالا