[알고리즘, C] 병합 정렬(Merge Sort)의 구현

<병합 정렬 구현>

[MergeSort.c]

/*
* 알고리즘 - 병합 정렬(Merge Sort)
* 파일명: MergeSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 병합 정렬 구현
* 이전 버전 내용:
*/

#include <stdio.h>
#include <stdlib.h>

// 병합 과정
void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int front_Idx = left; // 첫 번째 인덱스(가장 왼쪽)
	int rear_Idx = mid + 1; // mid(중간)의 바로 다음 -> 오른쪽의 맨 첫 번째 인덱스
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1)); // 정렬한 데이터를 담을 배열 동적 할당
	int sort_Idx = left; // 동적 할당에 쓰일 첫 인덱스

	// 첫 번째 인덱스가 mid와 같아지거나 (왼쪽에 나눈 배열의 끝까지 가는 경우)
	// 오른쪽의 인덱스가 right와 같아지거나 (오른쪽에 나눈 배열의 끝까지 가는 경우)
	while (front_Idx <= mid && rear_Idx <= right)
	{
		if (arr[front_Idx] <= arr[rear_Idx]) // 합쳐지기 전에 좌우에 나뉜 값에 대한 비교
			sortArr[sort_Idx] = arr[front_Idx++];
		else
			sortArr[sort_Idx] = arr[rear_Idx++];

		sort_Idx++;
	}

	// 병합 후 정렬이 끝나면
	if (front_Idx > mid)
	{
		for (i = rear_Idx; i <= right; i++, sort_Idx++) // 오른쪽 부분을 채움
			sortArr[sort_Idx] = arr[i];
	}
	else
	{
		for (i = front_Idx; i <= mid; i++, sort_Idx++) // 왼쪽 부분을 채움
			sortArr[sort_Idx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i]; // 원래 배열에 정렬된 값을 대입

	free(sortArr); // 할당 해제
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산
		mid = (left + right) / 2;

		// 둘로 나눠서 정렬 (재귀)
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		
		// 정렬이 된 배열을 병합
		MergeTwoArea(arr, left, mid, right);
	}

	
}

int main()
{
	int arr[7] = { 3, 2, 4, 1, 7, 6, 5 };
	int i;

	// 배열의 전체 영역을 정렬
	MergeSort(arr, 0, (sizeof(arr) / sizeof(int)) - 1);


	for (i = 0; i < 7; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

 

[병합 정렬의 이해]

병합 정렬은 분할 정복(Divide and Conquer)라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 기법이다.
분할 정복이란, 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할(divide)하여 정복(conquer)하는 방법이다.
단, 분할하여 정복한 후에는 결합(combine)하는 과정을 거쳐야 한다.
다음의 3단계를 거쳐 알고리즘을 디자인 하는 것이 분할 정복법이다.

1) 분할 (Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다.
2) 정복 (Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다.
3) 결합 (Combine) - 분할해서 해결한 결과를 결합하여 마무리한다.

병합 정렬은 위와 같은 방법을 근거로 다음과 같이 디자인되었다.

 

“8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고,

이걸 또 다시 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.”

그래서 병합 정렬은 데이터가 1개만 남을 때까지 분할을 해나간다.
데이터가 2개만 남아도 정렬을 해도 되지만, 데이터가 1개만 남으면 정렬을 할 필요가 없어지기 때문이다.
그래서 병합 정렬은 나누는 것이 핵심이 아니라, 병합되는 과정에서 정렬이 이뤄진다.
그렇기 때문에 ‘병합 정렬’이라는 이름이 붙은 것이다.

[성능 평가]

병합 정렬의 성능 평가는 비교연산의 횟수에 대해서는 MergeTwoArea 함수를 기준으로 한다.
병합 과정에서 정렬을 하게 되므로 여기서 비교 연산이 이뤄지기 때문이다.
그리고 데이터의 수에 따라서 진행하는 비교 연산의 횟수는 $log_2n$이다.

데이터의 수가 $n$개라고 하면 비교연산에 대한 빅-오는 $O(nlog_2n)$ 이 된다.
이동 연산의 경우, 위 코드를 기준으로 하면 크게 임시 배열에 데이터를 병합하는 과정에서 한 번.
그리고 마지막에 임시 배열에 저장된 데이터 전체를 원래 배열에 옮기는 데 한 번 발생한다.
그래서 이동 횟수는 최악, 평균, 최선의 경우와 상관 없이 $2nlog_2n$만큼 수행하게 된다.
그러므로 이동연산에 대한 빅-오는 $O(log_2n)$이 된다.