정렬 알고리즘 - 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

 

병합 정렬이란?

 - 분할 정복(divide and conquer) 알고리즘 디지인 기법에 근거하여 만들어진 정렬 방법.

 

 - 데이터가 1개 남을 때까지 분할하고, 분할된 데이터를 정렬한 후 다시 결합한다.

 

 - 실제 정렬은 분할하는 과정이 아니라, 병합하는 과정에서 이루어진다.

 

 - 병합 정렬은 O(nlogn)의 시간복잡도를 가진다.

 

 - 병합 정렬은 임시 메모리가 필요하다는 단점이 존재한다.

 

---

 

병합 정렬 예시(오름차순)

 

1. 초기 상태

 

 

2. 데이터가 1개 남을 때 까지 분할 한다.

 

 

3-1. 분할 된 데이터를 정렬하여 묶는다.

 

 

 

3-2. 정렬하여 묶은 결과

 

 

4-1. 3번에 의해 묶인 데이터를 다시 정렬하여 묶는다.

 

 

 

4-2. 정렬하여 묶은 결과

 

 

5-1. 4번에 의해 묶인 데이터를 다시 정렬하여 묶는다.

 

 

5-2. 정렬하여 묶은 결과(최종 결과)

 

 

---

 

 

병합 정렬의 정렬&결합 과정

 

 - 결합하는 두 데이터는 모두 정렬되어 있다.

 

 - 처음부터 하나씩 비교하여 임의의 데이터 공간에 저장한다.

 

1. 초기 상태(정렬되어 있는 두 개의 데이터)

 

 

2. 첫 번째 데이터의 인덱스(1)과 두 번째 데이터의 인덱스(1) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

 

3. 첫 번째 데이터의 인덱스(2)과 두 번째 데이터의 인덱스(1) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

 

4. 첫 번째 데이터의 인덱스(2)과 두 번째 데이터의 인덱스(2) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

 

5. 첫 번째 데이터의 인덱스(3)과 두 번째 데이터의 인덱스(2) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

 

6. 첫 번째 데이터의 인덱스(3)과 두 번째 데이터의 인덱스(3) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

 

7. 첫 번째 데이터의 인덱스(3)과 두 번째 데이터의 인덱스(4) 의 데이터를 비교한 후 더 작은 데이터를 넣는다.

8. 첫 번째 데이터의 인덱스(4)과 두 번째 데이터의 인덱스(4) 의 데이터를 비교한 후 더 작은 데이터를 넣는다

 

9. 마지막 데이터를 넣어 정렬을 완성한다.

 

---

 

병합 정렬 코드(C++)

#include <iostream>
#include <vector>

using namespace std;

void MergeData(vector<int> &vec, int left, int mid, int right)
{
	int firstIndex = left;
	int secondIndex = mid + 1;
	int i;

	int tmpIndex = left;
	// 정렬을 위한 공간 미리 선언 필요
	vector<int> tmp(vec.size());

	// 인덱스를 증가해 가면서 값을 비교하고, 데이터에 넣는다.
	while (firstIndex <= mid && secondIndex <= right)
	{
		if (vec[firstIndex] <= vec[secondIndex])
		{
			tmp[tmpIndex] = vec[firstIndex];
			firstIndex++;
		}
		else
		{
			tmp[tmpIndex] = vec[secondIndex];
			secondIndex++;
		}
		tmpIndex++;
	}

	// 첫 번째 데이터에 있는 값만 다 옮긴 경우
	if (firstIndex > mid)
	{
		// 두 번째 데이터에 있는 값을 그대로 옮긴다.
		for (int i = secondIndex; i <= right; i++, tmpIndex++)
		{
			tmp[tmpIndex] = vec[i];
		}
	}
	// 두 번째 데이터에 있는 값만 다 옮긴 경우
	else
	{
		// 첫 번째 데이터에 있는 값을 그대로 옮긴다.
		for (int i = firstIndex; i <= mid; i++, tmpIndex++)
		{
			tmp[tmpIndex] = vec[i];
		}
	}

	// 정렬된 데이터 복사.
	for (int i = left; i <= right; i++)
	{
		vec[i] = tmp[i];
	}

}

void MergeSort(vector<int> &vec, int left, int right)
{
	int mid;

	// 분할 가능한 경우
	if (left < right)
	{
		mid = (left + right) / 2;

		// left ~ mid에 위치한 데이터를 정렬한다.
		MergeSort(vec, left, mid);

		// mid+1 ~ right에 위치한 데이터를 정렬한다.
		MergeSort(vec, mid+1, right);

		// 정렬한 데이터를 병합한다.
		MergeData(vec, left, mid, right);


	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec{ 7,1,8,3,5,2};

	cout << "정렬 전 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;

	// right에는 크기가 아니라, 마지막 인덱스 값 전달.
	MergeSort(vec,0,vec.size()-1);

	cout << "정렬 후 : ";
	for (auto i : vec)
		cout << i << ", ";
	cout << endl;
	
	return 0;
}

 

실행 결과