[알고리즘] mergesort

분할정복법

mergesort, quicksort, heap sort 

 

mergesort는 분할정복법이라는 것인데 통째로 정복하는 것보다 각각을 정복하는 알고리즘 설계 전략 중 하나입니다.

 

-분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

-정복 : 각각의 작은 문제를 순환적으로 해결

-합병 : 작은 문제의 합을 합하여(merge) 원래 문제에 대한 해를 구함

 

 문제를 반으로 쪼갠 다음 작은 문제를 해결하기 위해서 또 다른 알고리즘을 고안할 필요는 없습니다. 원래 문제를 해결하는 동일한 방법으로 즉 recursion으로 해결하면 됩니다. 최대값을 찾기 위해 둘로 쪼개서 왼쪽 오른쪽 각각에서 최대값을 찾으면 되는 것입니다. 

 

합병에 해당하는 단계는 왼쪽 최대값과 오른쪽 최대값 중 더 큰 값을 찾는 것입니다. 분할정복법은 recursion을 사용해서 해결하는 기법이기도 합니다. 

 

1. 정렬할 데이터를 반으로 쪼개서 분할을 합니다.

2. 분할된 각각의 작은 문제들을 recursion으로 정렬을 합니다. 

3. 두 개의 정렬된 리스트를 합칩니다. 

 

mergesort

mergeSort(A[], p, r))  #A[p...r]을 정렬한다.
{
	if(p<r) then {
    	q <- (p+q)/2;
        mergeSort(A, p, q);
        mergeSort(A, q+1, r);
        merge(A, p, q, r);
    }
}

merge(A[], p, q, r)
{
	정렬되어 있는 두 배열 A[p...q]와 A[q+..r]을 합하여
    정렬된 하나의 배열 A[p...r]을 만든다.
}

p 처음 q중간 r마지막 

 

void merge(int data[], int p, int q, int r)
{
	int i = p, j = q + 1, k = p;
	int tmp[data.length()];
	while (i<=q && j<=r)
	{
		if (data[i] <= data[j])
			tmp[k++] = data[i++];
		else
			tmp[k++] = data[j++];
	}
	while (i <= q)
		tmp[k++] = data[i++];
	while (j <= r)
		tmp[k++] = data[j++];

	for (int i = p; i <= r; i++)
		data[i] = tmp[i];
}

 

데이터를 정렬할 때 하나의 추가 배열이 더 필요합니다.

 

MergeSort 알고리즘의 시간복잡도는 recursion의 틀을 가지고 있기 떄문에 for문의 반복횟수를 기준으로 시간복잡도를 보기에는 어렵습니다. 하지만 분할정복법의 시간복잡도는 쉽습니다. 

n/2개로 mergesort하는 것을 두번 해야 합니다. 그리고 전체가 n이기에 n이 추가됩니다.

 

O(n log n)이 됩니다.