시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
병합 정렬이란 무엇입니까?
정렬 병합 하는 재귀 절차. 또한 나누고 정복하다 연산. 이제 분할 및 정복 알고리즘이 무엇인지 알아야합니다. 이는 문제를 하위 문제로 나누고 가장 짧은 해결 된 하위 문제를 찾을 때까지 나누는 절차의 한 유형입니다. 가장 짧게 해결 된 하위 문제를 병합하여 큰 / 주요 문제에 대한 해결책을 찾습니다. 보자 연산 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)이며 상수입니다.
사용 된 알고리즘 유형
여기서는 분할 및 정복 접근 방식을 사용하여 병합 정렬을 해결합니다.
