병합정렬 (Merge Sort)

알고리즘 처음 배울 때 Merge Sort, Quick Sort에서 본격적으로 어려워 했던 기억이 난다.

재귀함수에 익숙하지 않으면 이해하기 어려운데 그림으로 천천히 따라가면 이해하기가 쉽다

https://ko.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort

 

분할 정복기법이라고 해서 

 

- 분할 : 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나눈다
- 정복 : 나눈 작은 문제를 각가 해결한다
- 통합 : 해결된 해답을 모은다

 

과정을 거치는 알고리즘이다 그림만 보면 어렵지 않은데 재귀적으로 호출 되고 정렬되고 합쳐진다는 개념이 생소했던 기억이 난다.

 

divide(분할) 와 merge(합병) 두가지 함수로 구성되었는데 각각 살펴보면

void divide(int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		divide(left, mid);
		divide(mid + 1, right);
		merge(left, right);
	}
}

 left, right는 배열의 시작과 끝이라고 생각하면 된다. 파라미터 이름을 start, end 이런식으로 짜는 사람도 있던 것 같다.

한번 divde 함수가 호출되면  처음부터 mid까지 mid에서 끝까지 이렇게 두 배열로 나눠서 진다 조건문에 따라 left 가 right 와 같거나 커질때 종료되므로 위 그림처럼 배열길이가 2일때까지 양쪽으로 나눠질 것이다. 여기서 중요한건 divde함수가 한번 호출될때마다 merge 함수도 한번 호출된다는 것 

즉, divde 함수(배열의 시작과 끝 인덱스로 시작) -> 배열 두개로 나눠짐(divide함수) -> 나눠진 각 divde함수에서 조건문 false 될때까지 재귀함수 호출됨 -> 조건문 false 되면 이때까지 호출된 divde함수들 안에 있는 merge함수가 실행됨

 

merge함수를 살펴보면 rst배열을 사용해서 정렬한걸 rst에 넣고 기존배열에 순서대로 rst값을 넣으면 끝이다

void merge(int left, int right) {
	int mid = (left + right) / 2;
	int i = left;
	int j = mid + 1;
	int k = left;
	int rst[20] = { 0, };

	// 양쪽의 리스트? 는 정렬 된상태고 이를 merge하는 함수이므로 양쪽리스트에서 최솟값 비교후 더 작은 값을 rst에 넣고 idx올려주고 반복
	while (i <= mid && j <= right) {
		if (arr[i] > arr[j]) {
			rst[k++] = arr[j++];
		}
		else {
			rst[k++] = arr[i++];
		}
	}
	// 위 반복문이 종료되는 조건 후 결과배열에 들어가지 못한 값을 순서대로 넣어주면 됨
	// 두개의 조건 중 하나라도 false되면 끝나기 때문에 남는 배열이 생길 수 있음 
	if (i > mid) {
		while (j <= right) {
			rst[k++] = arr[j++];
		}
	}
	else {
		while (i <= mid) {
			rst[k++] = arr[i++];
		}
	}
	// 원래 배열에 옮겨 담는 작업
	for (int m = left; m <= right; m++) {
		arr[m] = rst[m];
	}
}

주석 처리한 설명중에 중요한게 양쪽 배열(리스트 자료구조는 아니니까)은 이미 정렬된 상태라는 것

위 그림만 봐도 조건문 false될때까지 divide되고 즉, 나눠질 수 있는만큼 다 나눠지고 정렬되고 합쳐지는 순서니까

내가 두 배열을 합치려고 할때 이 두 배열은 각 각 정렬된 상태라는 것!

while문이 복잡해 보일 수 있는데 그냥 두배열 중에 최소값을 rst배열에 순서대로 넣는 것 뿐임

이렇게 넣고 나면 두 배열 중에 하나라도 다 넣으면 while  종료 후 두 배열 중 아직 다 rst에 안들어간 배열을 마저 rst에 넣어 주고 순서대로 원래 배열 arr에 넣어주면 끝!

 

전체 코드 : 

#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;


int arr[20];

void merge(int left, int right) {
	int mid = (left + right) / 2;
	int i = left;
	int j = mid + 1;
	int k = left;
	int rst[20] = { 0, };

	// 양쪽의 리스트? 는 정렬 된상태고 이를 merge하는 함수이므로 양쪽리스트에서 최솟값 비교후 더 작은 값을 rst에 넣고 idx올려주고 반복
	while (i <= mid && j <= right) {
		if (arr[i] > arr[j]) {
			rst[k++] = arr[j++];
		}
		else {
			rst[k++] = arr[i++];
		}
	}
	// 위 반복문이 종료되는 조건 후 결과배열에 들어가지 못한 값을 순서대로 넣어주면 됨
	// 두개의 조건 중 하나라도 false되면 끝나기 때문에 남는 배열이 생길 수 있음 
	if (i > mid) {
		while (j <= right) {
			rst[k++] = arr[j++];
		}
	}
	else {
		while (i <= mid) {
			rst[k++] = arr[i++];
		}
	}
	// 원래 배열에 옮겨 담는 작업
	for (int m = left; m <= right; m++) {
		arr[m] = rst[m];
	}
}
void divide(int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		divide(left, mid);
		divide(mid + 1, right);
		merge(left, right);
	}
}
int main() {


	srand(time(0));
	int max = 0;
	for (int i = 0; i < 20; i++) {
		arr[i] = rand() % 1000;
		if (max < arr[i]) max = arr[i];
	}
	cout << "### Before Sorting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}

	cout << endl;
	int size = sizeof(arr) / sizeof(int);
	divide(0,size-1);
	cout << "### After Sroting ###" << endl;
	for (int i = 0; i < 20; i++) {
		cout << arr[i] << " ";
	}

}