[알고리즘 / 분할정복] #1 합병 정렬 (Merge Sort)

합병 정렬 (Merge Sort)

 

입력값을 $1/2$로 분할하여 부분문제 크기를 감소시키는 분할 정복 알고리즘이다.

N개의 숫자의 배열을 N/2개씩 분할하고 재귀적 합병 정렬 후, 2개의 정렬된 부분을 합병하여 정렬한다.

즉, 합병 과정이 문제를 정복하는 것이다.

 

 

 

---

시간복잡도

 

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

합병 정렬은 분할 후 합병이 일어난다.

 

 

먼저 분할은 배열을 더이상 나눌서 없을때까지 2개의 배열로 나누는 재귀함수를 호출하는 것으로

O(1)의 시간이 걸린다.

 

 

이후 합병으로 넘어가면

2개의 정렬된 배열 A(크기 m개)와 B(크기n개)를 받으면 최대 비교 횟수는 (m+n-1)번이다.

합병시 두개의 숫자를 한번씩 비교할때, 더 작은 수가 결과 배열인 C에 저장된다.

따라서 배열 C는 A와 B의 모든 수(m+n)의 숫자들이 저장되나, 가장 마지막 수는 비교할 필요가 없으므로

최대 비교 수는 (m+n-1)이다.

따라서 합병의 시간복잡도는 O(m+n)이다.

 

 

 

결론

분할과 합병의 시간복잡도

분할 : $O(1)$

합병 : $O(m+n)$

 

 

---

 

 

이제 합병정렬의 시간복잡도를 구하기위해 합병을 층별로 살펴보는 것으로 계산할 수 있다.

 

 

 

 

 

위와 같이 크기가 8인 배열을 합병할때 숫자를 계속 반으로 나누어 3개의 층을 만들었다.

그렇다면 배열의 크기가 n개일때 몇개의 층이 만들어질까?

 

 

입력크기 (n)	예	층 (k)
$n$	$8$
$n/2$	$8/2 = 4$	1층
$n/4 = n/2^2$	$8/2^2 = 2$	2층
$n/8 = n/2^3$	$8/2^3 = 1$	3층

 

위와 같은 조건으로 나열해 보면 입력값을 지속적으로 반으로 나눴을때,

k번까지 반으로 분할하면 k개의 층이 생긴다.

즉, k는 $n = 2^k$이므로

지수인 k를 구하기위해 진수인 n과 아래 첨자로 2를 사용하여

$k = log_2n$

으로 정의될 수 있다.

로그에 대한 정의

mathbang.net/595

로그란, 로그의 정의

m.blog.naver.com/PostView.nhn?blogId=freewheel3&logNo=220853009691&proxyReferer=https:%2F%2Fwww.google.com%2F

로그, 지수를 표현하기 위해 배운다고?(이거 하나로 로그 끝내자!)

 

 

 

 

 

결과적으로 합병 정렬의 시간복잡도는 다음과 같다.

길이가 n인 배열을 k층수 만큼 반복하여 배열을 반으로 나누고 나눈 배열들을 병합한다.

1. 병합을 위한 두 배열의 비교는 n번을 넘기지 않는다. 예로, 2층에서 비교연산 횟수는, $2 * (n/4) = n$과 동일하다.

2. 1번의 예로 진행된 공식을 더이상 나눌수 없는 k번째 층에 적용하면 다음과 같다. $2 * (n/2^k) = nlog_2n$

 

즉, 합병 정렬의 시간복잡도는 다음 공식을 따른다.

$(층수) * O(n) = log_2n * O(n) = O(nlogn)$

 

 

---

 

공간복잡도

 

 

합병 정렬은 O(n)의 공간복잡도를 요구한다.

입력을 위한 메모리 공간 외에 추가로 입력과 같은 크기의 배열이 필요하기 때문이다.

이는, 2개의 정렬된 부분을 하나로 합병하기 위한 결과를 저장하는 배열이 필요하기 때문이다.

 

 

 

---

 

장점

 

 

합병 정렬은 외부정렬이 기본이 되는 정렬 알고리즘이다.

연결 리스트의 데이터를 정렬하는 것도 퀵 정렬이나 힙 정렬보다 훨씬 효율적이다.

멀티코어 CPU와 다수 프로세서로 구성된 그래픽 처리 장치(GPU)의 등장으로 정렬 알고리즘을 병렬화하는 것에 활용된다.

 

 

 

---

코드 예제

수도코드

MergeSort (A, x, y)
입력 : A[x]~A[y]
출력 : 정렬된 A[x]~A[y]

if ( x < y ) {                                  // 배열의 원소의 수가 2개 이상이면 실행
    k = [(x+y)/2]                             // k = 반으로 나누기 위한 중간 원소 인덱스

    MergeSort(A,x,k)                        // 앞부분 재귀 호출
    MergeSort(A,k+1,y)                    // 뒷부분 재귀 호출

    A[x]~A[k]와 A[k+1]~A[y]를 합병  // 합병
}

 

 

의사코드를 통해 다음을 확인할 수 있다.

1. 재귀함수를 호출함로 배열을 2개씩 나누는 결과를 반환한다. (시간복잡도 O(1))

2. 합병을 하는 부분은 합병될 두 배열의 크기만큼 반복한다. (시간복잡도 O(x + k), O((k+1) + y))

3. 위 과정을 $log_2(A의 길이)$번 반복한다.

 

 

이제 이를 코드로 전환하면 다음과 같아진다.

/// 합병정렬 함수
/// C++는 매개변수 배열은 주소값을 전달하기에 시작점과 끝점을 통해 추가적 메모리 할당없이 바로 배열에 변화를 적용할 수 있다.
/// <data1 : int A[]> 	정렬할 배열
/// <data2 : int begin> 정렬할 배열의 시작점
/// <data3 : int end> 	정렬할 배열의 끝점
void 합병정렬::MergeSort(int A[], int begin, int end) {
	int half = (begin + end) / 2;
	if (begin < end) {
		
		//재귀함수 호출
		MergeSort(A, begin, half);

		MergeSort(A, half + 1, end);

		/////////////////////////////////
		//합병 코드

		Merging(A, begin, end, half);
	}
}

 

 

재귀함수 호출로 배열을 다 나누어버린 상황에서 이제 합병 코드가 실행된다.

void 합병정렬::Merging(int A[], int begin, int end, int half) {
	int b = begin;			// 배열 시작지점
	int e = end;			// 배열 종료지점
	int h = half + 1;		// 배열 중간지점
	int resultPos = begin;	// 결과 배열의 승자표기를 위한 시작지점

	// 새로운 배열 할당
	int *result = NULL;
	result = new int[end - begin + 1];

	// while 라인은 좌측(begin부터 half)과 우측(half부터 end)이 각자의 끝을 넘기지 않은 상태이면 반복한다
	// 즉, 한쪽이 작은 수만 몰아져 있어도 일단 작은 수를 다 구별하면 반복하지 않겠다는 의미이다.
	// 이에대한 예외처리는 while문을 벗어나면 한다
	while (b <= half  && h <= end) 
    {
		// 이제 좌우측의 각 변수를 비교해야한다
        // 좌측 변수가 우측보다 작으면 result변수의 값에 삽입된다
		if (A[b] < A[h]) 
        {
			result[resultPos] = A[b];
			b++;
		}
        // 좌측이 우측보다 작지 않을 경우, 반대로 우측값이 result에 삽입된다
		else 
        {
			result[resultPos] = A[h];
			h++;
		}

		// 이제 결과의 다음 배열자리로 넘어가서 매 반복마다 배열에 더 작은 수가 차례대로 쌓인다
        resultPos++; 
	}


	// 하지만 만약 Alpha(최초의 배열)이 홀수인 경우 양쪽 배열의 크기가 맞지 않는다.
	// 이를 예외 처리해줄 방법을 선언해야한다

	// 1. A: [1][2][3], B: [3][4]와 같이 좌측 값이 지속적으로 작은 값이면 위의 b값만 증가한 경우
	//	  연산 마지막에 b가 증가연산자로 half를 넘어버린다. 그럼 나머지를 넣어주면 될 것이다
	//    *여기서 예시로든 B가 [4][3]과 같은 모습이 나올 수 없다. 재귀함수가 그들도 재정렬했기 때문이다
	
    int tmp;
    // 원본과 임시 배열을 넘기고 h가 끝난 지점부터 값을 반복해서 넣어주면 된다.
    // 뒷 배열에 값이 남았을 경우 남은 값을 넣어준다.
    // b가 절반보다 높으면 앞 배열은 이미 정리가 끝이 났다는 의미이며 뒷 배열에 번호를 확인한다.
    // * Result[1][2][3][3][4], A[1][2][3], B[3][4]
    //   b = 2, h = 4, half = 2
	if (b > half) 
    {
		tmp = h;
	}
    // 앞 배열에 값이 남았을 경우 남은 값을 넣어준다.
    // h가 끝자리보다 높으면 뒷 배열은 이미 정리가 끝이 났다는 의미이며 앞 배열에 번호를 확인한다.
	// * Result[1][3][4], A[1], B[4][3]
    //   b = 1, h = 2 half = 1
	else 
    { 
    	tmp = b;
	}

    // 
	for (; resultPos <= end; resultPos++, tmp++) 
    {
		result[resultPos] = A[tmp];
	}

	//마지막으로 result를 A에 넣는다. 배열은 이미 포인터이기 때문에 따로 값을 돌려줄 필요도 없다
    for (int i = begin; i <= end; i++) 
    {
		A[i] = result[i];
	}
    
	delete[] result;
	result = NULL;
}