[알고리즘] 병합정렬(MergeSort)

병합정렬을 공부하는게 아니라

"분할 정복" 알고리즘에 대해 공부한다 생각해야한다.

 

분할정복 알고리즘들의 원리와 접근법은 똑같기 때문이다.

너무 병합정렬 코드를 외우는데만 몰두하면 안된다는 것이다.

 

일단 병합정렬을 하려면 다음과 같은 일을 해야한다.

 

1. 배열을 계속 구간별로 쪼개 나누자.

( 함수호출도를 계속 그려나가보자. 전체적으로 보면 이진트리 느낌이다 )

2. 한 개씩만 남을때까지 계속 쪼갠다

3. 이제 각 묶음끼리 정렬하면서 병합한다.

4. 마지막으로 한 묶음이 될때까지 계속 병합한다.

( "계속" 에 밑줄 친 이유는 재귀를 암시하는 키워드기 때문이다)

 

---

[ MergeTwoArea ]

 

void MergeTwoArea(int* arr, int left, int mid, int right);
void MergeSort(int* arr, int left, int right);

병합정렬은 나누고 합치면서 정렬하는 방식이라

두 개로 나누는 함수와 나뉜 두개를 다시 붙여주는 함수

즉 총 2개의 함수가 필요하다.

 

---

[ MergeSort의 함수호출도 ]

 

MergeSort의 호출흐름이다.

 

 

 

이 원본 그림이 사실 굉장히 오만한 그림이다.

 

왼쪽 오른쪽 둘 다 동시에 진행되는거 같고 

양쪽 동시에 병합 병합 해서 완성되는거 같지만 

위와 같이 순서를 매겨보면 전혀 아니다.

 

위 그림에서 함수의 return 까지 고려하면 다음과 같다.

 

 

 이 마지막 그림을 통해서 MergeTwoArea 가 맨 코드상 맨 마지막 줄에 위치해야한다는 것을 알 수 있다.

 

void MergeSort(int* arr, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		MergeTwoArea(arr, left, mid, right);
	}
}

 

if문으로 묶어 놓은 이유는 일단 범위 1일때는 아무것도 할 일이 없기 때문이다.

범위가 2일때만 MergeTwoArea가 일어나면 되므로 left<right 이란 조건이 들어간 것이다!

 

---

[ MergeSort.c ]

 

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int* arr, int left, int mid, int right) {
	int fIdx = left;
	int rIdx = mid + 1;
	int sIdx = left;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));

	while (fIdx <= mid && rIdx <= right) {
		if (arr[fIdx] <= arr[rIdx]) {
			sortArr[sIdx++] = arr[fIdx++];
		}
		else {
			sortArr[sIdx++] = arr[rIdx++];
		}
	}

	if (fIdx > mid) {
		for (int k = rIdx; k <= right; k++) {
			sortArr[sIdx++] = arr[k];
		}
	}
	else {
		for (int k = fIdx; k <= mid; k++) {
			sortArr[sIdx++] = arr[k];
		}
	}

	for (int k = left; k <= right; k++) {
		arr[k] = sortArr[k];
	}

	free(sortArr);
}

void Mergesort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		Mergesort(arr, left, mid);
		Mergesort(arr, mid + 1, right);
		MergeTwoArea(arr, left, mid, right);
	}
}

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

	int* arr = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	Mergesort(arr, 0, N - 1);

	for (int i = 0; i < N; i++) {
		printf(" %d", arr[i]);
	}

	return 0;
}

 

---

여기서 중요한건 코드가 아니라 좀 꿀팁들이다.

 

 

1. 배열을 왜 right 로 해놨을까

 

 

이런 상황일때 4개만 병합하는 상황이여도

전체 개수만큼 배열을 할당한 뒤 

전체 배열에서의 실제 idx 위치로 저장해놓으면

 

맨 마지막에 실제 객체로 정렬된 임시배열 sortArr 에서 원소를 옮기는데 매우 간편하기 때문이다.

 

딱 4개만 생성한다면 

실제 진짜 idx로 만들기 위해 fIdx 값을 더 해야하는 아주 골치아프고 귀찮은 일이 발생한다.

이건 배워갈만한 점이다.

 

---

2. while문

// 둘 다 자기 범위를 돌고 있으면 
// while문 계속 돌기
while (fIdx <= mid && rIdx <= right) {

한 쪽을 다 돌아 

한쪽 원소들이 모두 sortArr 임시정렬배열에 들어갔다면

while문을 빠져나와야한다.

 

그리고 아래에 있는 남은 한쪽 원소들을 그냥 순서대로 집어넣으면 된다!

 

왜냐고?

이미 다 정렬되어 있으니까

이건 재귀로 아래에서부터 다 정렬되어 올라온 결과물이다

 

---

3. 마지막 if문

// 앞에꺼가 다 배치되었으면
if (fIdx > mid)

// 뒤에꺼 다 배치되었으면
// if(rIdx > right)
else

이게 방금 말한 한쪽이 다 배치되었으면

남은 한쪽 배치하는 코드.

무지성 복사해주면 된다 이거는. 이미 정렬되어있는거니까

 

 

 

하 너무 무지성으로 써서

이거 나중가면 내가 이해할 수 있을라나 모르겠네

뭐 일단 나중에 또 보면서 다듬는걸로 ㅇㅇ

내가 하고 싶은 말들은 다 써놓음