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

---

 

Merge Sort (병합정렬) 특징

1. 비교를 통해 정렬하는 비교기반 정렬 알고리즘
2. Divide & Conquer (분할 정복) 알고리즘
3. 시간 복잡도 : O(N*logN)
4. N크기의 임시 배열 1개가 추가적으로 필요

 

 

Merge Sort 과정 이해하기1 - 전체 Process

Merge Sort는 분할하여, 정렬한뒤, 이를 비교하면서 Merge하는 과정을 통해서 이루어진다. 

먼저, 배열에 2개의 Data가 있을 때, 오름차순으로 Merge Sort하는 과정을 살펴보자. 

Merge Sort (N=2)

3과 1을 분할한 뒤에, 각각을 정렬해야하지만, Data가 1개씩 있기 때문에 정렬할 필요가 없다. 

분할된 두 배열을 합칠 때, 비교하여 둘 중에 작은 수가 먼저 오도록 Merge 한다. 

 

 

 

 

이제 배열에 6개의 Data가 있을 때, 오름차순으로 Merge Sort하는 과정을 살펴보자. 

Merge Sort (N=6)

3개의 배열 2개로 분할한 뒤에, 각각의 배열을 정렬한 뒤에 Merge 하는 과정을 거친다. 

분할된 두 배열을 할칠 때, 비교하여 작은 수가 먼저 오도록 Merge 한다. 

 

 

 

 

Merge Sort 과정 이해하기2 - Merge Process

위의 N=6 일 때의 Merge 과정 중, "병합" 과정에 대해서 살펴보고자 한다. 

정렬되어 있는 2개의 배열을 서로 비교하면서, Merge 하는 과정인데,

실제 Code에서는 원래의 배열에서 2개의 구간으로 나눠진 것을 Merge 하게 된다. 

 

아래 그림으로 살펴보자. 

1. A[ i ]=1 와 A[ j ]=3를 비교하여, 작은 수를 tmp에 저장한다. 1이 작으므로, i를 1칸 이동시킨다. 
2. A[ i ]=5 와 A[ j ]=3을 비교하여, 작은 수를 tmp에 저장한다. 3이 작으므로, j를 1칸 이동시킨다. 
3. (반복)
4. i == m 이고, j == e 일때 종료된다. 

 

Merge 과정1

 

Merge 과정 2

 

 

---

 

Merge Sort 코드

앞에서 살펴본 과정들을 Code로 옮기면, Merge Sort 구현이 가능하다. 

Code는 아래의 4가지 단계로 구성된다. 

 

1. base condition : 종료 조건
2. divide & conquer : 중간을 기준으로 나눠서 재귀
3. merge : 나눠졌던 Data를 하나로 합치기 (임시 배열 활용)
4. copy : 임시 배열의 Data를 원래 배열에 복사

 

 

먼저 Merge Sort 함수를 살펴보자. 

const int MAX = 1000;
int N;
int A[MAX], trr[MAX];	// A: 원본 배열, trr: 임시 배열

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;		// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];	// 왼쪽 구간에 데이터가 남은 경우
	while (j <= e) trr[k++] = A[j++];	// 오른쪽 구간에 데이터가 남은 경우

	for (i = s; i <= e; i++) A[i] = trr[i];	// 4. copy
}

 

 

N개의 수를 입력받고, 정렬된 결과를 출력하는 코드를 짜보자. 

#include <stdio.h>

const int MAX = 1000;
int N;
int A[MAX], trr[MAX];	// A: 원본 배열, trr: 임시 배열

void mergeSort(int s, int e) {
	if (s >= e) return;		// 1. base condition

	int mid = (s + e) / 2;		// 2. divide & conquer
	mergeSort(s, mid);
	mergeSort(mid + 1, e);

	int i = s, j = mid + 1, k = s;		// 3. merge
	while (i <= mid && j <= e) {
		if (A[i] <= A[j]) trr[k++] = A[i++];
		else trr[k++] = A[j++];
	}
	while (i <= mid) trr[k++] = A[i++];	// 왼쪽 구간에 데이터가 남은 경우
	while (j <= e) trr[k++] = A[j++];	// 오른쪽 구간에 데이터가 남은 경우

	for (i = s; i <= e; i++) A[i] = trr[i];		// 4. copy
}

int main() {
	scanf("%d", &N);		// N 입력

	for (int i = 1; i <= N; i++) {
		scanf("%d", A + i);	// N개의 수 입력
	}

	mergeSort(1, N);	// Sorting

	for (int i = 1; i <= N; i++) {
		printf("%d", A[i]);	// 출력
	}

	return 0;
}

 

---

 

연습문제 추천

[Beginner][백준] 2751번 : 수 정렬하기 2

[Beginner][백준] 2751번 : 수 정렬하기 2

 

[Beginner][백준] 24060번 : 알고리즘 수업 - 병합 정렬 1

[Beginner][백준] 24060번 : 알고리즘 수업 - 병합 정렬 1