merge sort - 병합 정렬 정리

이번에 알고리즘 공부를 하며 알게 된 merge sort에 대해서 정리를 해보겠습니다.

이 sort를 이해하기 위해서는 기본적으로 재귀함수에 대해서 알고 계셔야합니다.

재귀함수란 함수 자신이 자신을 다시 부르는 함수를 의미합니다.

그리고 재귀함수 내에서 정해진 return에 알맞은 조건을 만족하게 되면 return을 하여 값을 도출하는 형태입니다.

글로만 설명하니 너무 어려운것 같아서 재귀함수부터 간단히 그림으로 설명드리겠습니다.

이처럼 자신의 복사본을 불러서 계산을 하고 return되는 조건에 알맞으면 return이 되는 형식을 재귀함수라고 부른다.

검은 글자가 자신의 복사본을 늘려가는 과정이고 붉은 글씨가 int값이 정해져서 return되고 있는 상황입니다.

처음으로 이렇게 그림을 그려서 설명을 해봤는데 그림 그리는게 힘드네요..

이제 재귀함수도 설명을 했으니 merge sort로 가보겠습니다.

제가 복습할 때도 그렇고 블로그에 들어와주신 다른 분들도 동일하게 코드를 먼저 보고 이해가 되는 것이 좋은 방향이니 코드 부터 올리겠습니다.

void merge(int a[], int low, int mid, int high) {		//머지소트
	int b[10000];
	int i = low, j = mid + 1, k = 0;

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

	while (i <= mid) {
		b[k] = a[i];
		i++;
		k++;
	}

	while (j <= high) {
		b[k] = a[j];
		j++;
		k++;
	}
	k--;
	while (k >= 0) {
		a[low + k] = b[k];
		k--;
	}

}
void mergesort(int a[], int low, int high) {
	if (low < high) {
		int m = (low + high) / 2;

		mergesort(a, low, m);

		mergesort(a, m + 1, high);

		merge(a, low, m, high);
	}
	else {
		return;
	}
}

여기서 low는 정렬을 시작할 배열의 첫번째 요소의 위치 high는 배열의 마지막 요소의 위치로 입력을 해주시면 됩니다.

b라는 배열의 크기는 필요한만큼 크기를 키우면 됩니다.

 

기본적인 정렬 방법은 배열을 반으로 나누어서 한쪽을 정렬하고 다른 한쪽을 정렬하는것 입니다.

재귀함수처를 이용하여 계속해서 반으로 나누게 됩니다. 반으로 나누다가 low<high가 true가 아닐 때 정렬할 숫자가 마지막에 도달한 과정입니다.

마지막에 도달하였다는 것은 더 이상 반으로 나눌 수 없는 상황을 의미하며 1개만 있을 때를 의미합니다.

이렇게 1개만 남아있을 때 다른 한쪽에서도 1개만 남아 있는 상황이 되어 있을 것입니다.

이때 그 둘이서  sort를 하게 됩니다. 이게 왼쪽의 상황이라면 오른쪽에 있던 아이들도 sort가 되어 return이 되었을 것입니다.

그러면 왼쪽 모임과 오른쪽 모임이 서로 다시 sort를 하게 됩니다. 이때 중요한 것은 이미 왼쪽과 오른쪽 모두 sort가 진행되어 있는 모양이라는 것입니다.

그렇기에 왼쪽의 1번째 인자와 오른쪽의 1번째 인자들을 비교하여 위 코드처럼 오름차순일 경우 크기가 작은 것이 1번째 인자로 들어가고 크기가 큰것은 계속 남습니다.

예시를 들어 왼쪽< 오른쪽 상태라면 왼쪽의 1번째 인자는 정리되는 배열 b에 들어가게 되고 왼쪽은 2번째 인자를 가리키게 되며 오른쪽은 변하지 않고 1번째 인자를 가리키는 상태라는 의미입니다.

 

이런 방식으로 반으로 나누어져 있는 것을 반씩 sort를 하며 전체적인 sort를 만드는 방식입니다.