[알고리즘/C++] 합병 정렬 Merge Sort

# 문제 설명

n 개의 자연수 배열을 병합 정렬을 이용해 오름차순으로 정렬한다.

# 입출력 예

입력	출력
8 7 6 3 1 5 2 4 8	1 2 3 4 5 6 7 8

 

# 문제 풀이

#include <stdio.h>
using namespace std;
int arr[101], tmp[101];

void d(int left, int right){
	int mid;
	int p1, p2, p3;
	if(left<right){
    	
        // (1) 배열을 같은 크기의 2개 배열로 분리한다.
		mid=(left+right)/2;
		d(left, mid);
		d(mid+1, right);
		
        // (2) 정렬 및 대입을 위해 포인터 역할을 할 변수를 준비한다.
		p1=left;
		p2=mid+1;
		p3=left;
		
        // (3) 값을 비교하여 정렬한다.
		while(p1<=mid && p2 <= right){
			if(arr[p1] < arr[p2]) tmp[p3++] = arr[p1++];
			else tmp[p3++] = arr[p2++];
		}
        
        // (4) (3)번 계산이 끝난 후 더이상 계산이 필요없는 부분을 마저 대입한다.
		while(p1<=mid) tmp[p3++] = arr[p1++];
		while(p2<=right) tmp[p3++] = arr[p2++];
		
        // (5) 원 배열에 다시 대입한다.
		for(int i=left; i<=right; i++)
			arr[i] = tmp[i];
	}
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &arr[i]);
	
	d(1,n);	// (0) 재귀함수 호출
	
	for(int i=1; i<=n; i++)
		printf("%d ", arr[i]);
	return 0;
}

# 설명

0. 재귀 함수 호출.

for(int i=1; i<=n; i++)
	scanf("%d", &arr[i]);
d(1,n);

배열을 읽어들 일 때 1 ~ n 범위에 대입했기 때문에

인수에 1, n 을 넣어서 호출합니다.

 

배열을 한 줄로 세워놨다고 가정하고

1은 가장 왼쪽 끝에 있기 때문에 left

n은 가장 오른쪽 끝에 있기 때문에 right 라고 생각합니다.

 

 

1. 배열을 같은 크기의 2개 배열로 분리한다.

void d(int left, int right);

함수의 매개 변수로 left 와 right 를 받았기 때문에

두 값의 평균값으로 mid 값을 구합니다.

mid=(left+right)/2;
d(left, mid);
d(mid+1, right);

그리고 left ~ mid 배열과 mid + 1 ~ right 배열로 나누면

같은 크기의 2개의 배열로 구분할 수 있습니다.

그렇게 왼쪽 배열과 오른쪽 배열로 나눠진 재귀함수를 호출합니다.

 

재귀함수는 if 문의 조건을 통해

left 와 right 가 같아진 배열. 즉 한 개의 값만 남기 직전까지 호출 될 것입니다.

 

재귀 함수 아래쪽 부분들은 후위 순회를 하기 때문에

더 이상 나눌 수 없는 배열을 가리키는 함수들이 종료된 이후 부터

다시 역순으로 실행될 것입니다.

 

다시 말해, 8개 값을 가진 배열을 가리키는 함수부터 재귀 호출되어 4개, 2개, 1개를 가리키게 될 때

1개 함수의 아랫 부분은 if문 조건에 걸려 실행되지 않고,

2개 함수의 아랫부분부터 실행됩니다.

 

 

2. 정렬 및 대입을 위해 포인터 역할을 할 변수를 준비한다.

p1=left;
p2=mid+1;
p3=left;

p1 과 p2 는 원 데이터가 들어있는 arr 배열의 참조값을 가리키는 포인터 역할을 합니다.

p3 는 임시 데이터가 들어갈 tmp 배열의 참조값을 가리키는 포인터 역할을 합니다.

 

p1은 현재 함수에서 가리키는 배열의 가장 왼쪽값인 left 를 갖게되고,

p2는 현재 함수에서 가리키는 배열의 중간값 + 1 을 갖습니다.

 

재귀함수를 통해 배열들이 반으로 나뉘어 왔고,

다시 재귀함수들이 차례로 종료되면서 2배로 들어나기 때문에

p1과 p2가 절반씩 참조하는 것이 효율적일 것입니다.

즉, p1은 0~50%까지, p2는 51%~100% 까지 탐색하는 것을 담당하는 것입니다.

 

 

3. 값을 비교하여 정렬한다.

while(p1<=mid && p2 <= right){
	if(arr[p1] < arr[p2]) tmp[p3++] = arr[p1++];
	else tmp[p3++] = arr[p2++];
}

while문의 조건문이 바로

p1은 0% ~ 50%의 범위를 가리키고

p2는 51% ~ 100%의 범위를 가리킬 때라는 의미가 되겠습니다.

 

이 곳에서 실질적인 비교 정렬이 실행됩니다.

오름차순 정렬이기 때문에

왼쪽 값(p1이 가리키는 값)이 오른쪽 값(p2가 가리키는 값)보다 적으면 왼쪽값을 임시 배열 tmp에 넣고,

아니라면 오른쪽 값을 임시 배열 tmp에 넣습니다.

 

처음 2개 범위의 배열을 가리키는 함수 시점에서는 

arr[1] 과 arr[2] 를 비교하여 작은 값을 임시배열 tmp에 넣을 것입니다.

 

그리고 while문 조건에 따라 p1이 mid보다 커지거나, p2가 right보다 커지면서 while문이 종료됩니다.

 

 

4. (3)번의 계산이 끝난 후 더 이상 계산이 필요없는 부분을 마저 대입한다..

while(p1<=mid) tmp[p3++] = arr[p1++];
while(p2<=right) tmp[p3++] = arr[p2++];

p1이 mid보다 커졌다면 (p2 <= right) 조건은 아직 참이고,

p2가 right보다 커졌다면 (p1 <= mid) 조건이 아직 참이기 때문에

남은 값을 마저 대입하게 됩니다.

 

만약 8개 범위의 배열 값이 1,2,3,4,5,6,7,8 일 때 정렬을 했다면

p1이 가리키는 '1'과 p2가 가리키는 '5' 부터 비교하기 때문에

왼쪽 부분의  1,2,3,4가 먼저 전부 tmp 배열에 대입될 것입니다.

나머지 5, 6, 7, 8들도 이전 2개, 4개 함수를 거치면서 정렬되어 합병되었기 때문에

그대로 tmp 배열에 대입하여 주면 됩니다.

 

 

5. 원래 배열에 다시 대입한다.

for(int i=left; i<=right; i++)
	arr[i] = tmp[i];

정렬이 끝났다면 임시 배열 변수 tmp에서 다시 원래 배열 변수인 arr 로 대입해줍니다.

 

끝.