합병 정렬(Merge sort)

버블 정렬, 삽입 정렬, 선택 정렬은 단순한 알고리즘들이지만 정렬하는데 시간이 많이 든다는 커다란 단점이 있다. 즉 자료가 많을때 이들 정렬 방법들을 부적절하고 보다 빠른 정렬 알고리즘이 필요하다. 이번에는 좀 더 빠른 정렬 방법중 하나인 합병 정렬(merge sort)에 대해 살펴보겠다.

 

합병 정렬?

합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이 정렬 방법은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 분할 정복 기법이란 하나의 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 방법을 말한다. 분할 정복 기법은 대개 순환 호출을 이용하여 구현된다. 분할 정복 기법에서 말하는 알고리즘 설계하는 요령은 아래와 같다.

• Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
• Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
• Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

분할 정복 기법을 적용하면 합병 정렬은 다음의 단계들로 이루어진다.

• Divide : 입력 배열을 같은 크기이 2개의 부분 배열로 분할한다.
• Conquer : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
• Combine : 정렬된 부분 배열들을 하나의 배열에 통합한다.

분할 정복 기법의 개념

위 그림은 분할 정복 기법의 개념을 나타낸다. 처음 21,10,12,20,25,13,15,22가 배열에 있다고 가정하자. 이 배열을 더 이상 분할할 수 없을때까지 분할한다. 그럼 21,10,12,20,25,13,15,22 숫자들이 각각 한개씩 분할되고, 그 이후 이 숫자들을 정렬하고 정렬된 숫자들을 통합하는 과정을 통해 최종적으로 정렬된 배열인 12,12,13,15,20,21,22,25을 얻게 된다.

 

합병 정렬 알고리즘의 예제

• 배열에 27,10,12,20,25,13,15,22이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자
• 2개의 정렬된 리스트를 합병하는 과정
  • 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮긴다
  • 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다
  • 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트로 복사한다
  • 새로운 리스트를 원래의 리스트로 옮긴다

합병 정렬 예제

합병 정렬 구현

#include <iostream>

#define MAX_SIZE	1024

using namespace std;

static void merge(int *A, int left, int mid, int right)
{
	int i, j, k = left, l;
	static int sorted[MAX_SIZE];
	//분할 정렬된 A의 합병
	for (i = left, j = mid + 1; i <= mid && j <= right;)
	{
		sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];
	}

	if (i > mid)
	{
		for (l = j; l <= right; l++, k++)
		{
			sorted[k] = A[l];
		}	
	}
	else
	{
		for (l = i; l <= mid; l++, k++)
		{
			sorted[k] = A[l];
		}
	}

	//배열 sorted[]의 리스트를 배열 A[]로 재복사
	for (l = left; l <= right; l++)
	{
		A[l] = sorted[l];
	}
}

//합병 정렬을 이용해 int배열을 오름차순으로 정렬하는 함수
void mergeSort(int *A, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2; // 리스트의 균등 분할
		mergeSort(A, left, mid); // 부분 리스트 정렬
		mergeSort(A, mid + 1, right); // 부분 리스트 정렬
		merge(A, left, mid, right); // 합병
	}
}

void printArray(int *A, int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << A[i] << " ";
	}
	cout << endl;
}

int main()
{
	int A[8] = { 27,10,12,20,25,13,15,22 };
	int len = sizeof(A) / sizeof(int);

	printArray(A, len);
	mergeSort(A, 0, len-1);
	printArray(A, len);

	return 0;
}
            

 

합병 정렬의 복잡도 분석

합병 정렬은 순환 호출 구조로 되어 있다. 따라서 레코드의 개수 n이 2의 거듭제곡이라고 가정하고 순환 호출의 깊이가 얼마나 되는지를 분석해보자. 만약 n=2^3인 경우에는 부분 배열의 크기가 2^3->2^2->2^1->2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 따라서 일반적으로 n=2^k라고 하면 부분 배열의 크기는 2^k->2^k-1->...->2^0이 되어 순환 호출의 깊이가 k가 된다. 이때 k=log_2n가 된다.

 

배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산은 수행되지 않는다. 부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행되는 것이다. 그리고 순환 호출의 깊이만큼의 합병 단계가 필요하다. 그러면 각 합병 단계에서는 몇 번의 비교 연산이 수행될까?

위 그림에서 볼 수 있다시피 일반적으로 합병 단계에서 총 비교 연산은 최대 nlog_2n번 필요 한것을 알 수 있다.

 

이동 연산은 얼마나 수행되는 것일까? 

하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 되므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서 log_2n개의 합병 단계가 필요하므로 총 2nlog_2n개의 이동 연산이 필요하다. 결론적으로 합병 정렬은 O(nlog_2n)의 복잡도를 가지는 알고리즘이다.

 

합병 정렬의 특징은 입력 데이터가 어떻게 이루어져 있는지에 상관없이, 최악, 평균, 최선의 경우에도 모두 동인한 시간에 정렬된다는 것이다. 단점은 임시 배열이 필요한 것과 만약 레코드들의 크기가 큰 경우에는 이동횟수가 많아 큰 시간적 낭비가 발생할 수 있다는 것이다. 그러나 레코드 자체를 이동하지 않고 포인터(또는 링크 인덱스)만 이동하면 이런 문제가 해결된다. 따라서 합병 정렬은 매우 효율적인 정렬 방법이 하나이다.