합병 정렬(Merge sort)을 구현해보자

개인적으로 공부하는 내용이므로 틀린 부분이 있을 수 있습니다. 있다면 알려주세요 :)

Merge sort는 분할정복법(Divide and Conquer)을 사용한다. 분할정복을 사용하는 대표적인 정렬 알고리즘은 퀵 소트, 머지 소트, 힙 소트가 있다. 분할정복이란 해결하고자 하는 하나의 큰 문제를 동일한 크기의 여러개의 분할로 나누고, 분할된 작은 문제를 해결(정복)하여 합병을 통해 합쳐주는 것이다.

각각의 문제를 순환적으로 해결하기 위해 보통 재귀를 사용한다.  머지 소트의 동작을 그림으로 나타내면 다음과 같다.

https://www.faceprep.in/c/merge-sort-in-c/

 

정렬이 되지 않은 배열 {4, 8, 13, 2, 23, 16}이라는 하나의 큰 문제를 동일한 크기로 재귀적으로 분할한다. 가장 작은 크기인 1개의 분할에 도달하면 각 분할을 정렬된 상태로 합친다. 이를 계속해서 반복하면 결국엔 정렬된 배열 하나가 완성된다. 

우선 머지 소트를 수행하는 함수를 간단히 설계해보면 다음과 같다.

// vec의 [p, q] 범위의 요소를 정렬합니다.
void MergeSort(vector<int>& vec, const size_t p, const size_t q);

// vec의 [p, r], [r+1, q] 범위의 두 배열을 정렬해서 합칩니다.
void Merge(vector<int>& vec, const size_t p, const size_t r, const size_t q);

 

MergeSort 함수는 vec(배열)에 대해 인덱스 [p, q] 범위의 요소들을 정렬한다. 내부적으로 재귀적인 호출을 통해 배열을 분할하고 합칠 것이다.

Merge 함수는 2개로 나뉘어진 범위의 배열을 정렬하여 합친다. MergeSort 내에서 호출된다.

 

다음은 MergeSort 함수의 루틴이다. 

// vec의 [p, q] 범위의 요소를 정렬합니다.
void MergeSort(vector<int>& vec, const size_t p, const size_t q)
{
    // 1. p가 q보다 작을 때만 수행합니다.
    
    // 2. 분할할 중간 지점을 기록합니다.
    
    // 3. 첫 지점부터 중간지점까지 범위의 배열(A)을 정렬합니다.
    
    // 4. 중간 지점부터 마지막 지점까지 범위의 배열(B)을 정렬합니다.
    
    // 5. 배열 A와 B를 합병합니다.
}

 

1. 머지 소트는 분할의 크기가 1이 될 때까지 수행하므로 p가 q보다 작을 때만 수행한다는 조건이 필요하다. 즉 p와 q가 동일할 때 수행하지 않는다. 분할의 크기가 1일 경우 p와 q가 동일할 것이다. 

 

2. 하나의 배열을 최대한 동일한 크기로 분할해야 한다. 따라서 두 지점의 중간 지점을 구한다. 중간 지점은 r로 표시하며 (p+q)/2 를 이용한다. 아래의 예에서 r은 (0+3)/2 = 1이다.

 

3, 4. 중간 지점을 기준으로 나뉘어진 두 배열에 대하여 각각 MergeSort 함수를 호출하여 재귀적으로 수행한다.

 

5. 위 두 배열을 각각 A, B라 할 때 다음과 같이 정합쳐서 하나의 정렬된 배열로 만든다.

 

이를 코드로 표현하면 다음과 같다.

void MergeSort(vector<int>& vec, const size_t p, const size_t q)
{
    if(p < q)
    {
    	size_t r = (p+q)/2;
        
        MergeSort(vec, p, r);
        MergeSort(vec, r+1, q);
        Merge(vec, p, r, q);
    }
}

 

 

다음은 Merge 함수의 루틴이다. 

void Merge(vector<int>& vec, const size_t p, const size_t r, const size_t q)
{
    // 1. [p, q] 범위와 동일한 크기의 임시 배열을 하나 생성합니다.
    
    
    // 2. [p, r], [r+1, q] 범위의 두 배열의 첫 원소부터 각각 비교하여
    // 오름차순으로 임시 배열에 차례대로 저장합니다.
    
    
    // 3. 임시 배열을 기존 배열인 vec의 [p, q] 범위에 덮어 씌웁니다. 
}

 

1. 두 배열을 합친 결과를 임시로 저장하기 위해 [p, q]와 동일한 크기의 임시 배열을 생성한다.

2. 두 배열의 첫 원소부터 각각 비교해가며 오름차순으로 임시 배열에 차례대로 저장한다.

 

3. 임시 배열을 원본의 위치에 덮어 씌운다.

 

이를 코드로 표현하면 다음과 같다.

void Merge(vector<int>& vec, const size_t p, const size_t r, const size_t q)
{
	size_t i = p;
	size_t j = r + 1;

	vector<int> tmp(q - p + 1);

	size_t base = 0;
	while (i <= r && j <= q)
	{
		// 오름차순 정렬
		if (vec[i] <= vec[j])
		{
			tmp[base++] = vec[i++];
		}
		else
		{
			tmp[base++] = vec[j++];
		}
	}

	// 두 번째 배열의 원소들이 남았을 경우
	if (i == r + 1)
	{
		copy(vec.begin() + j, vec.begin() + (q + 1), tmp.begin() + base);
	}
	else if(j == q + 1)
	{
		copy(vec.begin() + i, vec.begin() + (r + 1), tmp.begin() + base);
	}


	copy(tmp.begin(), tmp.end(), vec.begin() + p);
}