62. 병합정렬 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★☆

#include <stdio.h>

int n, a[101], temp[101];

void Divide(int lt, int rt)
{
	int mid;
	int p1, p2, p3;
	if(lt < rt)
	{
		mid = (lt+rt) / 2;
		Divide(lt, mid);
		Divide(mid+1, rt);
		
		p1 = lt;
		p2 = mid+1;
		p3 = lt;
		
		while(p1 <= mid && p2 <= rt)
		{
			if(a[p1] < a[p2]) temp[p3++] = a[p1++];
			else temp[p3++] = a[p2++];
		}
		while(p1 <= mid) temp[p3++] = a[p1++];
		while(p2 <= rt) temp[p3++] = a[p2++];
		
		for(int i = lt; i <= rt; i++)
			a[i] = temp[i];
	}
}


int main()
{
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
		
	Divide(1, n);

	for(int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	return 0;
}

1. 숫자의 개수 n, n개의 숫자를 저장할 배열 a, 각 숫자를 비교하기 위한 포인터 p1, p2, 비교한 숫자를 저장하기 위한 배열 temp, 배열 temp의 idx를 지정할 포인터 p3를 선언한다.

2. 여기서 중요한 것은 포인터 p1, p2, p3 와 이분탐색을 위한 변수 mid 는 반드시 지역 변수로 선언해야한다.

지역 변수로 선언하지 않고 전역 변수로 선언하면 각 재귀함수들이 이 값을 공유해 오류를 일으킬 수 있다.

 

n = 8

먼저 8개의 숫자들을 전부 1개씩 남을 때까지 분리한다.

mid = (lt+rt) / 2; // 반으로 분리 (1-4), (5-8)
Divide(lt, mid); // (1-4)를 또 반으로 분리
Divide(mid+1, rt); // (5-8)을 또 반으로 분리

가장 작은 단위까지 분리하고나면 가장 작은 단위부터 비교하여 작은 숫자가 왼쪽으로 가게 재배치하면 된다.

p1 = lt;
p2 = mid+1;	
p3 = lt;
		
while(p1 <= mid && p2 <= rt)
{
    if(a[p1] < a[p2]) temp[p3++] = a[p1++];
    else temp[p3++] = a[p2++];
}
while(p1 <= mid) temp[p3++] = a[p1++];
while(p2 <= rt) temp[p3++] = a[p2++];
		
for(int i = lt; i <= rt; i++)
	a[i] = temp[i];

 

p1 = lt = 1

p2 = mid +1 = 1+1 = 2

p3 = lt = 1

 

while(p1 <= mid && p2 <= rt)

여기서 mid는 1이고, rt 는 2이다.

즉 1부터 1까지와 2부터 2까지 비교하겠다는 의미이다.

배열 a

      p1▼                 p2▼

7

6

3

1

5

2

4

8

배열 temp

      p3▼

p1 > p2 이므로 temp[p3++] = a[p2++]

while(p1 <= mid && p2 <= rt) 에 의해 p2 > rt가 되어 break;

 

배열 temp

      p3▼

6

나머지 조건인 p1 <= mid 가 끝나지 않은 상태에서 break 되었기 때문에 while(p1 <= mid) temp[p3++] = a[p1++] 을 한다.

 

배열 temp

                              p3▼

6

7

이후 반복하면 그림과 같다.