시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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)이며 상수입니다.
사용 된 알고리즘 유형
여기서는 분할 및 정복 접근 방식을 사용하여 병합 정렬을 해결합니다.
