알고리즘 - 합병정렬

알고리즘 - 합병정렬

 

1개가 남을 때까지 나눈다.(DIVIDE),

합친다.

 

mergesort 와 merge는 2:1의 관계에 있다. 재귀이기 때문에 -> 스택을 이용한다.

 

mergesort함수의 소스코드

 

void mergesort(int n, keytype S[]){
	if(n>1){
	   const int h = n/2, m = n-1;
	   keytype U[h], V[m];
	   for(int I = 0; i<h;i++){
		U[i] = S[i];
	   }
           int index =0 ;
	   for(int I = h+1; i<n; I++){
	   	V[index] = S[i];
		index++;
		}
	   mergesort(h,U);
	   mergesort(m,V);
	   merge(h,m,U,V,S);
	}
}

 

 

merge함수의 소스코드

 

void merge(int h, int m, const keytype U[]. const keytype V[]. const keytype S[]){
	index I,j,k;
	I = 1; j=1; k=1;
	while(i<=h && j<=m){
	    if (U[i] < V[j]) {
		S[k] = U[i];
		I++;
	    }
	    else{
		S[k] = V[j];
		j++;
	    }
	   k++;
	}
	if(i >h)
		copy V[j] through V[m] to S[k] through S[h+m];
	else 
		copy U[i] through U[h] to S[k] through S[h+m];

 

합병정렬의 merge 시간복잡도

 

단위연산 : U[i]와 V[j]의 비교

U배열의 개수가 h개, V배열의 개수가 m개라고 했을 때 비교연산이 최악의 경우라도 h+m-1번인 것을 확인할 수 있다.

즉 W(h,m) = h+m-1이라고 볼 수 있다.

 

 

합병정렬의 전체 시간복잡도

 

mergesort할 때 n을 반으로 분리한 W(2/n)만큼 걸린다는 것을 알 수 있고, 이는 두 번 일어나기 때문에 2*W(2/n)이다. 또한, merge를 할 때는 앞에 언급한 것과 같이 h+m-1이라고 볼 수 있고, h+m은 n이기 때문에 총 시간 복잡도는 2*W(2/n)+n-1로 정의할 수 있다.

W(1) = 0 -> 합병이 전혀 이루어지지 않으므로,

 

이러한 복잡도는 도사정리를 통하여 W(n) = O(nlogn)가 된다.

 

 

합병정렬의 공간복잡도 분석

반씩 나눠지기 때문에 처음에는 n만큼 필요하지만 점점 2/n의 크기 두 개, 4/n만큼의 크기 네 개 등의 메모리가 필요하게 된다. 이는 2n이 되는데 2n은 O(n)이라고 할 수 있다.