정렬 병합


난이도 중급
자주 묻는 질문 아마존 Apple 부메랑 커머스 골드만 삭스 그루퍼 Microsoft 신탁 Paytm 퀄컴 스냅 딜 타겟 코퍼레이션
분열과 정복 정렬

병합 정렬이란 무엇입니까?

정렬 병합 하는 재귀 절차. 또한 나누고 정복하다 연산. 이제 분할 및 정복 알고리즘이 무엇인지 알아야합니다. 이는 문제를 하위 문제로 나누고 가장 짧은 해결 된 하위 문제를 찾을 때까지 나누는 절차의 한 유형입니다. 가장 짧게 해결 된 하위 문제를 병합하여 큰 / 주요 문제에 대한 해결책을 찾습니다. 보자 연산 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

시간 복잡성

O (N * log N) 여기서 N은 배열에있는 총 수입니다. 위 구현의 반복 관계는 다음과 같습니다. 티 (N) = 2 * T (N / 2) + O (1).

공간 복잡성

O (1) 여기서 우리는 주어진 배열을 제외하고 추가 공간을 만들지 않았으므로 공간 복잡성은 O (1)이며 상수입니다.

사용 된 알고리즘 유형

여기서는 분할 및 정복 접근 방식을 사용하여 병합 정렬을 해결합니다.

참조