වර්ග කිරීම ඒකාබද්ධ කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බූමරන්ග් වාණිජ්‍යය ගෝල්ඩ්මන් සැක්ස් ග්‍රෝෆර්ස් මයික්රොසොෆ්ට් ඔරකල් Paytm Qualcomm Snapdeal ඉලක්ක සංස්ථාව
බෙදන්න සහ ජය ගන්න වර්ග කිරීම

ඒකාබද්ධ කිරීමේ වර්ග කිරීම යනු කුමක්ද?

වර්ග කිරීම ඒකාබද්ධ කරන්න යනු පුනරාවර්තන ක්රියා පටිපාටිය. එය ද අ බෙදී ජය ගන්න ඇල්ගොරිතම. ඇල්ගොරිතම බෙදීම හා යටත් කර ගැනීම යනු කුමක්දැයි දැන් අප දැනගත යුතුය. එය එක්තරා ආකාරයක ක්‍රියා පටිපාටියක් වන අතර එමඟින් අපි ගැටළුව උපප්‍රශ්නවලට බෙදා කෙටිම විසඳුම උපප්‍රොබ්ලය සොයා ගන්නා තෙක් ඒවා බෙදන්නෙමු. කෙටිම විසඳූ උප ගැටළුව ඒකාබද්ධ කිරීමෙන් විශාල / ප්‍රධාන ගැටලුවට විසඳුම අපට ලැබේ. අපි බලමු ඇල්ගොරිතමය merge_sort සඳහා.

ඇල්ගොරිතම

පියවර 1 ගැටළුව උපප්‍රශ්න 2 කට බිඳ දමන්න.

පියවර 2 උපප්‍රශ්න අවම ප්‍රමාණයකට (විසඳන උපප්‍රශ්නය) ළඟා වන තෙක් පුනරාවර්තන ලෙස අමතයි.

පියවර 3 විසඳන ලද උප ගැටළු ඒකාබද්ධ කරන්න.

දැන්, උදාහරණය වෙත යන්න මෙම ඇල්ගොරිතම ක්‍රියාත්මක වන ආකාරය තේරුම් ගැනීම?

සඳහා පැහැදිලි කිරීම වර්ග කිරීම ඒකාබද්ධ කරන්න

වර්ගීකරණය නොකළ N අංකය සහිත A අරාවක් අප සතුව ඇත. 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

කාල සංකීර්ණත්වය

ඕ (එන් * ලොග් එන්) මෙහි N යනු අරාවෙහි ඇති මුළු සංඛ්‍යාවයි. ඉහත ක්‍රියාත්මක කිරීමේ පුනරාවර්තන සම්බන්ධතාවය වේ ටී (එන්) = 2 * ටී (එන් / 2) + ඕ (1).

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) මෙහි දී අපි ලබා දී ඇති අරාව හැර වෙනත් අමතර ඉඩක් නිර්මාණය කර නැත, අවකාශයේ සංකීර්ණතාව O (1) වන අතර එය නියත වේ.

භාවිතා කරන ඇල්ගොරිතම වර්ගය

ඒකාබද්ධ කිරීමේ වර්ග කිරීම විසඳීම සඳහා මෙහිදී අපි බෙදීම් සහ ජය ගැනීමේ ප්‍රවේශය භාවිතා කරමු.

ආශ්රිත