შერწყმა დალაგება


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Apple ბუმერანგის კომერცია Goldman Sachs გროფერები microsoft Oracle Paytm Qualcomm Snapdeal Target Corporation
Დაყავი და იბატონე დახარისხება

რა არის შერწყმის დალაგება?

შერწყმა დალაგება არის რეკურსიული პროცედურა. ის ასევე არის ა დაყოს და იპყროს ალგორითმი. ახლა უნდა ვიცოდეთ რა არის ალგორითმი დაყოფა და დაპყრობა? ეს არის პროცედურის ტიპი, რომელშიც ჩვენ დავყოფთ პრობლემას ქვეპროფლიმებად და ვყოფთ მანამ, სანამ არ აღმოვაჩენთ უმოკლეს ამოხსნას. უმოკლეს ამოხსნის ქვეპროგრამის შერწყმით ვპოულობთ დიდი / მთავარი პრობლემის გადაწყვეტას. მოდით ვნახოთ ალგორითმი merge_sort– ისთვის.

ალგორითმი

Ნაბიჯი 1 დაყავით პრობლემა 2 ქვეპრობლემად.

Ნაბიჯი 2 ქვეპროგრამები რეკრუტულად რეკავს მანამ, სანამ არ მიაღწევს მინიმალურ ზომას (ამოხსნილი ქვეპრობლემა).

Ნაბიჯი 3 ამოხსნილი ქვეპროგრამების შერწყმა.

ახლა გადადით მაგალითზე იმის გაგება, თუ როგორ მუშაობს ეს ალგორითმი?

განმარტება ამისთვის შერწყმა დალაგება

ავიღოთ, გვაქვს A მასივი, რომელიც შეიცავს 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 * ჟურნალი N) სადაც N არის მასივში არსებული საერთო რიცხვი. ზემოთ მოყვანილი განხორციელების განმეორებადი მიმართებაა T (N) = 2 * T (N / 2) + O (1).

სივრცის სირთულე

O (1) აქ ჩვენ არ შევქმენით რაიმე დამატებითი სივრცე მოცემული მასივის გარდა, ასე რომ, სივრცის სირთულე არის O (1), რომელიც მუდმივია.

გამოყენებული ალგორითმის ტიპი

აქ ჩვენ ვიყენებთ მიყოფის და დაპყრობის მიდგომას შერწყმის დალაგების გადასაჭრელად.

ლიტერატურა