[정렬 알고리즘] 3. 병합 정렬(Merge Sort)

[정렬 알고리즘]

1. 선택 정렬

2. 버블 정렬

3. 병합 정렬

4. 퀵정렬

5. 힙정렬

6. Counting Sort

_________________________________

🔎병합 정렬이란?

Divide And Conquer 알고리즘 중 하나로, 주어진 배열을 반으로 나누어 각각의 배열을 정렬한 뒤 병합하는 것을 재귀적으로 반복한다.

 

_______________________________________

🔎병합 정렬 알고리즘

1. 배열을 반으로 나눈다.

2. 각각의 배열을 병합 정렬한다.

3. 두 개의 배열을 합친다.

$\leftarrow$ 두 개의 정렬된 배열을 정렬된 배열로 합친다. 즉 병합정렬은 원소 하나짜리 배열까지 나누었다가 그것을 합치는 과정에서 정렬이 일어난다.

 

 

📌 배열을 합치는 방법

1. $A$의 반절이고, 정렬된 두 개의 배열을 각각 $p$배열과 $q$배열이라 하자.

3. $A$와 길이가 같은 $tmp$배열을 생성

4. $p$배열과 $q$배열의 원소를 비교한다.

5. $p[i]<q[j]$ $\rightarrow$ $tmp[t]$ 에 $p[i]$을 넣고, $i++$, $t++$

   $p[i]\geqq[j]$ $\rightarrow$ $tmp[t]$ 에 $q[j]$을 넣고, $j++$, $t++$

6. 1~5의 과정을 반복한다.

7. 만약 $i>q$이거나 $j>r$이면 두 배열 중 하나의 배열이 전부 $tmp$에 들어간 것이므로 반복을 그만둔다

8. 두 배열 중 남은 원소가 있는 배열이 있으면( $i\leq q or j \leq r$ 이면) 그 배열의 원소들을 $tmp$에 넣는다.

merge(A[], p, q, r){
	//A배열이 p~q까지 정렬되어 있고, q+1~r까지 정렬되어 있음

	i<-1, j<-1, t<-1;
    
    while(i<=q and j<=r){
    	if(p[i]<=q[i]){
        	tmp[t]<-p[i];
            t++;
            i++;
        }
        else{
        	tmp[t]<-q[j];
            t++;
            j++;
        }
    }
    
    while(i<=q){
    	tmp[k++]<-p[i++];
    }
    while(j<=r){
    	tmp[k++]<-q[j++];
    }
    
    i<-1;
    while(i<=r){
    	A[i]<-tmp[i];
        i++;
    }
}

 

📌 배열을 정렬하는 방법

 

mergeSort(A[], p, r){
	//A배열이 p~q까지 정렬되어 있고, q+1~r까지 정렬되어 있음
    if(p<r) then{
    	q <- ⌊(p+q)/2⌋
    	mergeSort(A[], p, q); //divide
    	mergeSort(A[], q+1, r); //divide
    	merge(A[], p, q, r); //conquer
    }
}

 

___________________________

 

🔎복잡도 분석

📌 시간복잡도

$\Theta(nlogn)$

 

분석 방식 1. Recurrence relation

$n=2^k$를 가정 ^[각주:1]

$T(n) = 2T(n/2) + n$

$\leq 2^kT(n/2^k) + kn$

$\in \Theta(nlogn)$

 

$T(n/2^k)=T(1)$ 일 때 $k=logn$이라서 저렇게 정리됨

상식적으로 병합이 n 걸리는데(cn일수도 있지만 상수무시) 깊이가 logn이라서 병합도 logn번 일어나기 때문이라고 생각할 수 있다.

 

분석 방식 2 : master theorem 활용

master theorem에 따라 f(n)=O(h(n)) 이면 T(n) = O(h(n)logn)

여기서 f(n)=h(n)=n

 

📌 공간복잡도

$O(n)$ 

1. 입출력 memory : n

2. Extra memory : n(tmp 배열을 위한 메모리) + logn(재귀 호출을 위해 stack에 함수를 쌓아놓기 위한 메모리)

따라서 O(n+n+logn) = O(n)

 

* 공간복잡도는 이 둘의 합이다.

 1. 입출력 memory : 입출력을 위해 반드시 필요한 메모리 공간

2. Extra memory : 알고리즘 내에서 문제 해결을 위해 별도로 사용하는 메모리 공간

 

____________________

🔎장단점

장점

1. $O(n^2)$ 정렬 알고리즘에 비해 빠르다.

2. Worst case, Best case 모두 $O(nlogn)$

 

단점

1. 복사가 많이 일어나서 복사가 느린 언어에 적합하지 않다.

2. 공간복잡도가 크다.

1. 모든 n과 2n 사이에는(n은 자연수) 반드시 $2^k$형태의 수가 있다. 그리고 다항식 시간복잡도 하에서 n과 2n의 인풋은 차이가 없다. 상수 무시가 가능하기 때문. 따라서 $2^k$일 때의 분석은 n일때의 분석, 2n일때의 분석 이 둘과 같은 복잡도를 가진다. (가정: 복잡도는 단조증가함수.)  [본문으로]