Merge Sort (병합정렬)

Merge Sort는 Devide and Conquer의 예시가 될 수 있는 알고리즘입니다.

이때, Devide and Conquer란? 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘을 말한다.

이를 병합정렬을 통해 알아보자.

다음 예시는 Devide의 예시로 3 4 1 5 2 라는 배열을 크기가 1이 될 때까지 분할한 모습이다.

그리고 이후 Conquer의 예시로 분할되어 있던 배열을 끼리 합쳐서 계속 정렬해서 결론적으로 다시 5개의 배열의 크기가 되었을때, 완전히 정렬된 모습이 된 것을 볼 수있다.

이렇듯 Merge Sort는 두 가지 큰 틀로 구성된다.

이를 의사코드로 구현해 보면 다음과 같다.

MergeSort(A,p,q)
입력: A[p]~A[q]
출력: 정렬된 A[p]~A[q]
1. if ( p < q ) { // 배열의 원소의 수가 2개 이상이면
2. k = ⌊(p+q)/2⌋ // k: 반으로 나누기 위한 중간 원소의 인덱스
3. MergeSort(A,p,k) // 앞부분 재귀 호출
4. MergeSort(A,k+1,q) // 뒷부분 재귀 호출
5. A[p]~A[k]와 A[k+1]~A[q]를 합병한다.
}

Line 1

• 정렬할 부분의 원소의 수가 2개 이상일 때에만 다음 단계 수행. 만일 n=1이면, 그 자체 로 정렬된 것이므로 어떤 수행을 할 필요 없이 이전 호출했던 곳으로 리턴

Line 2

• 정렬할 부분의 원소들을 ½ 로 나누기 위해, k = ⌊(p+q)/2⌋를 계산. 즉, 원소의 수가 홀수인 경우에는 k는 소수점 이하를 버림

Line 3~4

• MergeSort(A,p,k)와 MergeSort(A,k+1,q)를 재귀 호출하여 각각 정렬

Line 5

• line 3~4에서 각각 정렬된 부분을 합병
• 합병 과정의 마지막에는 임시 배열에 있는 합병된 원소들을 배열 A로 복사. 즉, 임시 배열 B[p]~B[q]를 A[p]~A[q]로 복사

C언어 코드로 구현

#include <stdio.h>
#define MAX_SIZE 100

int sorted[MAX_SIZE]; // merge 함수에서 정렬을 위한 임시 배열로 사용

void merge(int input[], int left, int mid, int right) { // 합병 함수
	int a, b, c, d;
	a = left; // 가장 왼쪽 위치
	b = mid + 1; // 중간값 + 1 의 위치
	c = left;

	while (a <= mid && b <= right) { // a가 중간 값보다 위치가 작거나 같으면서 b가 가장 오른쪽 위치보다 적게 위치한경우 실행 
		if (input[a] <= input[b]) {
			sorted[c++] = input[a++];
		}

		else {
			sorted[c++] = input[b++];
		}
	} // a와 b에 위치한 값을 비교하고 더 작은 값인 경우 그 값을 sorted 배열안에 넣고 해당 값을 인덱스 값을 + 1 해준다.

	// 위 과정이 끝난 후 남아있는 값들은 그냥 넣어준다.
	if (a <= mid) {
		for (int i = a; i <= mid; i++) {
			sorted[c++] = input[i];
		}
	}

	else if (b <= right) {
		for (int i = b; i <= right; i++) {
			sorted[b++] = input[i];
		}
	}
	//

	// sorted배열 안에 정렬된 값들을 input 배열 안에 넣어준다.
	for (int i = left; i <= right; i++) {
		input[i] = sorted[i];
	}
}

void merge_sort(int input[], int left, int right) { // 머지 소트 함수

	if (left < right) { // 왼쪽
		int mid = (left + right) / 2; // 중간값 계산
		merge_sort(input, left, mid); // 가장 왼쪽에서 중간 위치까지의 정렬
		merge_sort(input, mid + 1, right); // 중간 위치 + 1 부터 오른쪽 위치까지 정렬
		merge(input, left, mid, right); // 위의 두 정렬된 배열을 합병
	}

}

int main() {
	int input_count = 0; // 배열안에 넣을 입력 값의 개수
	printf("입력 값의 개수를 입력해주세요 : ");
	scanf("%d", &input_count);

	int input[MAX_SIZE]; // 입력 값의 배열

	for (int i = 0; i < input_count; i++) {
		scanf("%d", &input[i]);
	} // 입력 값 입력

	merge_sort(input, 0, input_count - 1);

	// 결과값 출력 코드
	printf("\n결과\n");
	for (int i = 0; i < input_count; i++) {
		printf("%d ", input[i]);
	}

	return 0;
}