B형 필수 정렬 : 머지 소트 Merge Sort

삼성 B형 전체 링크

 

B형에서는 Quick 정렬을 Reference 코드로 제공한다.

하지만, Quick은 최악의 경우 O(N²)이므로, 어떤 상황에서도 O(NlogN)인 Merge Sort를 익혀두자.

 

Merge Sort는 반으로 나누어서, 왼쪽을 정렬하고, 오른쪽을 정렬한 후, 합치는 방법으로 정렬을 한다.

왼쪽을 정렬할 때는, 다시 반으로 나누어서, 왼쪽, 오른쪽 정렬하고 합친다.

오른쪽도 마찬가지로 ...

 

즉, 재귀 함수를 이용해서 정렬하게 된다.

 

start >= end면 더 이상 정렬할 수 없으므로 종료 조건으로 사용한다.

void sort(int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1; /* 절반으로 나눈다 */
    
	sort(start, mid); /* 왼쪽 정렬 */
	sort(mid + 1, end); /* 오른쪽 정렬 */ 
	merge(start, end); /* 합친다 */
}

절반으로 나눌 때는 나누기 2를 사용해도 되지만, 비트 연산 >> 1이 조금 더 성능에 도움이 될 수 있다.

 

merge를 할때는 임시 배열이 원래 배열의 크기 만큼 필요하게 된다.

왼쪽과 오른쪽을 합칠 때, 순서대로 다른 배열에 합친 후, 다시 원래 배열에 가져다 줘야 하기 때문이다.

int a[100];
int b[100];

void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1; /* 절반으로 나눈다 */
	i = start; /* 왼쪽의 가장 낮은 index */
	j = mid + 1; /* 오른쪽의 가장 낮은 index */
	k = 0; /* 임시 배열의 index */

	while (i <= mid && j <= end) 
	{
		if (a[i] <= a[j]) b[k++] = a[i++]; /* 왼쪽 vs 오른쪽 비교해서 작은 것부터 복사 */
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++]; /* 남은 왼쪽 배열을 b로 */
	while (j <= end) b[k++] = a[j++]; /* 남은 오른쪽 배열을 b로 */

	for (i = start; i <= end;i++)
		a[i] = b[i - start]; /* b를 다시 a로 copy */

}

 

merge에서 배열을 반으로 쪼갠 후, 합치게 되는데, 왼쪽과 오른쪽 중 작은 것을 먼저 임시 배열(b)에 복사한다.

 

그림으로 확인해 보자.

 

merge는 왼쪽은 왼쪽대로, 오른쪽은 오른쪽대로 정렬이 된 후 실행하도록 보장된다.

따라서 아래의 예시대로 a 배열이 만들어진다면,

 

index i = a[start] = 1을 가르키게 되고

index j = a[mid + 1] = 2를 가르키게 된다.

 

a[i] <= a[j] 조건을 만족하므로, index i에 있던 1이 b 배열로 복사되고 i는 증가한다.

 

이제 i, j를 비교하면 j가 더 작으므로 j가 증가하고 b에는 2가 복사된다. (b[k++] = a[j++])

 

같은 방법으로 계속 진행하면 최종적으로 아래와 같은 결과가 된다.

index i > mid가 되었으므로 첫 번째 while문이 종료된다.

 

이제 while (j <= end) b[k++] = a[j++]; 로 남은 a가 b에 복사된다.

i > mid이기 때문에 while (i <= mid) b[k++] = a[i++];는 실행되지 않는다.

즉, 반드시 아래 2개의 while문 중 1개만 실행된다.

 

마지막으로 b를 다시 a로 옮겨 줘야한다.

현재 코드가 실행된 곳은 전체 a 배열이 아닌, 특정 구역의 start 부터 end이다.

 

따라서 a[start] = b[0] 이 된다.

 

배열을 합치는 연습은 링크에서 참고하자.

 

전체 코드는 아래를 참고 하자.

여러 배열을 sort할 때는 sort, merge 함수에 포인터를 추가로 넘겨주도록 만들면 된다.

#include <stdio.h>

int b[100];

void merge(int* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end;i++)
		a[i] = b[i - start];
}

void sort(int* a, int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1; 
	sort(a, start, mid);
	sort(a, mid + 1, end);
	merge(a, start, end);
}

int main(void)
{
	int a[] = { 10, -2, 5, 4, 3, 7, 10, -2, 1, -3 };
	int length = sizeof(a) / sizeof(int);

	sort(a, 0, length - 1);

	for (int i = 0; i < length;i++) printf("%d\n", b[i]);

	return 0;
}

 

실행 결과 정렬이 잘 된 것을 확인할 수 있다.

 

연습 문제로 BOJ 2751 수 정렬하기를 풀어보자.

---

아래의 코드에서 b[i - start]를 하는데, k를 start 부터 시작하면 조금 더 개선할 수 있다.

	for (i = start; i <= end;i++)
		a[i] = b[i - start];

 

즉, 굳이 k가 0부터 시작할 필요는 없다. 

sort에서 나눈 만큼 해당 배열의 메모리를 쓰기 때문이다.

 

k = start 부터 시작하면 마지막에 a[i] = b[i]가 된다.

void merge(int* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = start;

	...
    
	for (i = start; i <= end;i++)
		a[i] = b[i];
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

int b[100];

void merge(int* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = start;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end;i++)
		a[i] = b[i];
}

void sort(int* a, int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1; 
	sort(a, start, mid);
	sort(a, mid + 1, end);
	merge(a, start, end);
}

int main(void)
{
	int a[] = { 10, -2, 5, 4, 3, 7, 10, -2, 1, -3 };
	int length = sizeof(a) / sizeof(int);

	sort(a, 0, length - 1);

	for (int i = 0; i < length;i++) printf("%d\n", b[i]);

	return 0;
}