അടുക്കുക അടുക്കുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ബൂമറാങ് കൊമേഴ്‌സ് ഗോൾഡ്മാൻ സാക്സ് ഗ്രോഫേഴ്സ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ Paytm ക്വാൽകോം സ്നാപ്ഡേൽ ടാർഗെറ്റ് കോർപ്പറേഷൻ
ഭിന്നിപ്പിച്ചു കീഴടക്കുക ക്രമപ്പെടുത്തൽ

ലയനം തരംതിരിക്കൽ എന്താണ്?  

അടുക്കുക അടുക്കുക ഒരു ആണ് ആവർത്തന നടപടിക്രമം. ഇത് ഒരു വിഭജിച്ച് ജയിക്കുക അൽഗോരിതം. അൽഗോരിതം എന്താണ് വിഭജിച്ച് കീഴടക്കുകയെന്ന് ഇപ്പോൾ നമ്മൾ അറിയേണ്ടതുണ്ട്? ഇത് ഒരു തരം നടപടിക്രമമാണ്, അതിൽ ഞങ്ങൾ പ്രശ്‌നത്തെ ഉപപ്രൊബ്ലെമുകളായി വിഭജിക്കുകയും ഏറ്റവും ചുരുങ്ങിയത് പരിഹരിച്ച ഉപപ്രൊബ്ലം കണ്ടെത്തുന്നതുവരെ അവ വിഭജിക്കുകയും ചെയ്യുന്നു. ഏറ്റവും ചുരുങ്ങിയത് പരിഹരിച്ച സബ്പ്രൊബ്ലം ലയിപ്പിക്കുന്നതിലൂടെ വലിയ / പ്രധാന പ്രശ്നത്തിന് പരിഹാരം കണ്ടെത്താം. നമുക്ക് നോക്കാം അൽഗോരിതം ലയന_സോർട്ടിനായി.

അൽഗോരിതം  

ഘട്ടം 1 പ്രശ്നം 2 ഉപപ്രശ്നങ്ങളായി വിഭജിക്കുക.

ഘട്ടം 2 ഏറ്റവും കുറഞ്ഞ വലുപ്പത്തിലേക്ക് (പരിഹരിച്ച സബ്പ്രൊബ്ലം) എത്തുന്നതുവരെ സബ്പ്രൊബ്ലെംസ് ആവർത്തിച്ച് വിളിക്കുന്നു.

ഘട്ടം 3 പരിഹരിച്ച ഉപപ്രശ്നങ്ങൾ ലയിപ്പിക്കുക.

ഇപ്പോൾ, ഉദാഹരണത്തിലേക്ക് നീങ്ങുക ഈ അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് മനസിലാക്കുന്നുണ്ടോ?

വിശദീകരണം അടുക്കുക അടുക്കുക  

ക്രമീകരിക്കാത്തതിൽ N നമ്പർ അടങ്ങിയ ഒരു അറേ A ഉണ്ടെന്ന് നമുക്ക് എടുക്കാം. A = {9,1,4,2,5,3,7,2,6,17}

അടുക്കുക അടുക്കുക

അടുക്കുക അടുക്കുക

അടുക്കുക അടുക്കുക

അടുക്കുക അടുക്കുക

അടുക്കുക അടുക്കുക

അടുക്കുക അടുക്കുക

എട്ടാം ഘട്ടത്തിൽ ഞങ്ങൾക്ക് ഫൈനൽ ലഭിച്ചു അടുക്കിയ ശ്രേണി 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 * ലോഗ് N) ഇവിടെ ഒരു അറേയിലെ ആകെ സംഖ്യ N ആണ്. മുകളിലുള്ള നടപ്പാക്കലിന്റെ ആവർത്തന ബന്ധം T (N) = 2 * T (N / 2) + O (1).

ഇതും കാണുക
വ്യത്യസ്ത ഘടകങ്ങളുള്ള സബ്‌റേകൾ

ബഹിരാകാശ സങ്കീർണ്ണത  

O (1) ഇവിടെ നൽകിയിരിക്കുന്ന അറേ ഒഴികെ അധിക സ്ഥലമൊന്നും ഞങ്ങൾ സൃഷ്ടിച്ചിട്ടില്ല, അതിനാൽ സ്‌പേസ് സങ്കീർണ്ണത O (1) ആണ്, അത് സ്ഥിരമാണ്.

ഉപയോഗിച്ച അൽഗോരിതം  

ലയനം തരംതിരിക്കുന്നതിന് ഞങ്ങൾ ഇവിടെ വിഭജനവും ജയിക്കുന്ന സമീപനവും ഉപയോഗിക്കുന്നു.

അവലംബം