5. 분할과 정복_병합정렬(Merge Sort)

#분할과 정복을 이용한 정렬

-병합정렬

-퀵정렬

 

#분할과 정복 알고리즘

1. 큰 문제를 작은 문제들로 나눈다.

2. 단계1의 작은 문제들의 해를 재귀적으로 구한다.

3. 단계2에서 구한 작은 문제들의 해를 이용하여 원래 문제의 해를 구한다.

 

#병합정렬 알고리즘

1. 주어진 크기가 n인 리스트를 크기가 n/2인 두 부분으로 나눈다.

2. 크기가 n/2인 두 부분을 재귀적으로 정렬한다.

3. 정렬된 두 부분을 하나로 병합한다.

 

merge sort

 

 

#구현

#include <iostream>
using namespace std;

int* sorted;

void mergesort(int a[], int first, int last);
void merge(int a[], int first, int mid, int last);

int main(){
    int size;
    cin>>size;
    sorted = new int[size]; //정렬 후 배열
    int* a = new int[size]; //정렬 전 배열
    for(int i=0; i<size; i++) cin>>a[i];
    
    mergesort(a,0,size-1);
   
   for(int i=0; i<size; i++) cout<<a[i]<<" ";
   delete[] a;
   return 0;
}

void mergesort(int a[], int first, int last){
    if(first<last){
        int mid=(first+last)/2;
        mergesort(a,first,mid);
        mergesort(a,mid+1,last);
        merge(a,first,mid,last);
    }
}

void merge(int a[], int first, int mid, int last){
	int i=first; //왼쪽 배열의 첫 번째 인덱스
    int j=mid+1; //오른쪽 배열의 첫 번째 인덱스
    int k=first; //sorted의 첫 번째 인덱스
    
    //두 집합의 원소들 비교해서 더 작은 원소를 sorted 배열에 넣기
    while(i<=mid && j<=last){
        if(a[i]<=a[j]){
            sorted[k]=a[i];
            i++;
        }
        else{
            sorted[k]=a[j];
            j++;
        }
    }
    
    //남은 원소 sorted에 넣기
    if(i>mid){ //오른쪽 원소는 모두 sorted에 담긴 상태
        for(int t=j; t<=last; t++){
            sorted[k]=a[t];
            k++;
		}
	}
	else{ //왼쪽 원소는 모두 sorted에 담긴 상태
        for(int t=i; t<=mid; t++){
            sorted[k]=a[t];
            k++;
        }
    }

    for(int t=first; t<=last; t++)
        a[t]=sorted[t];
}
    

 

#시간복잡도

n=1인 경우 -> T(n) = 0 

n>1인 경우 -> T(n) ≤ 2T(n/2) + n

                          ≤ 2( 2T(n/4) + n )+n

                          ...

                          ≤ (2^k)T(n/(2^k)) + k*n

즉,  n=2^k 일 경우, T(n) ≤ n*T(1) + (log n)*n = 0 + n log n

 

크기가 n인 배열을 분할할 때 원소가 하나가 될때까지 반으로 나누기 때문에 log n의 시간이 들고,

병합할 때 while을 통해 모든 원소를 비교하기 때문에 n의 시간이 든다.

따라서 병합정렬의 시간복잡도는 T(n): O(n log n) 이다.

 

#병합정렬의 단점

- 병합할 때 O(n) 추가적인 메모리가 필요하다.(in-place가 아니다)

- O(log n)의 스택 메모리가 필요하다.