[merge sort] 머지소트 개념 및 구현

merge sort 개념

• 퀵소트처럼 대표적인 divide & conquer 알고리즘 중 하나.
• merge sort는 퀵소트와 비교했을 때, 안정적으로 nlogn의 시간복잡도를 내는 알고리즘이다.
• 퀵소트, 힙정렬에 비해서 메모리사용량이 더 많다.
• 평균적으로는 퀵소트보다 더 오래걸린다.
• 따라서 특수한 케이스가 아니라면 머지소트보다는 퀵소트를 더 많이 사용한다.

머지소트개념은 나누어서 정리해서 합친다는 개념이다.

여기서는 더 이상의 개념설명은 하지 않겠다.

 

 

merge sort 구현

머지소트를 구현함에 있어서 나는 두가지 방법으로 접근했다.(결과는 같다)

 

1. 직관적, 순차적인 접근 : divide를 최소단위가 될 때 까지 시행하고서 conquer하는 접근

2. 재귀적인 접근 : divide를 해서 두 개의 part가 생기면 각각을 conquer. --> conquer안에서는 다시 divide 와 conquer를 실행한다.

 

1번 코드는 아래와 같다.

#include <iostream>
#define MAX 10
using namespace std;

void MergeSort(int arr[], int l, int r);
void Conquer(int arr[], const int l, const int r);
void Divide(int arr[], int l, int r);

int tmp[MAX];

void Divide(int arr[], int l, int r)
{
	if (l < r)
	{
		int m = (r + l) / 2;
		Conquer(arr, l, m);
		Conquer(arr, m + 1, r);
	}
}

void Conquer(int arr[], const int l, const int r) // 이거 아닌거같음...
{
	Divide(arr, l, r); // divide 명령을 하면 하위 part들은 모두 정렬되서 올라온다고 생각하면 된다.
	int m = (l + r) / 2;
	int i = l, ll = l;
	int j = m+1;

	// 두 part중에 모두 비어진 part가 하나라도 없는경우
	while (i <= m && j <= r)
	{
		if (arr[i] < arr[j])
			tmp[ll++] = arr[i++];
		else
			tmp[ll++] = arr[j++];
	}

	//두 part중 하나가 다 비어진경우
	while (i <= m)
		tmp[ll++] = arr[i++];

	while (j <= r)
		tmp[ll++] = arr[j++];

	//tmp를 다시 arr에 복사한다.
	for (int i = l; i <= r; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeSort(int arr[], int l, int r)
{
	Conquer(arr, l, r);
}
int main()
{
	int arr[MAX] = { 3,5,6,1,2,4,0,9,7,8 };

	MergeSort(arr, 0, MAX-1);
	
	for (int i = 0; i < MAX; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;

	return 0;
}

 

 

2번 코드는 아래와 같다.

#include <iostream>
#define MAX 10
using namespace std;

void MergeSort(int arr[], int l, int r);
void Conquer(int arr[], const int l, const int r);
void Divide(int arr[], int l, int r);

int tmp[MAX];

void Divide(int arr[], int l, int r)
{
	if (l < r)
	{
		int m = (l + r) / 2;
		Divide(arr, l, m);
		Divide(arr, m + 1, r);
		Conquer(arr, l, r);
	}
}

void Conquer(int arr[], const int l, const int r)
{
	int m = (l + r) / 2;
	int i = l, ll = l;
	int j = m + 1;

	// 두 part중에 모두 비어진 part가 하나라도 없는경우
	while (i <= m && j <= r)
	{
		if (arr[i] < arr[j])
			tmp[ll++] = arr[i++];
		else
			tmp[ll++] = arr[j++];
	}

	//두 part중 하나가 다 비어진경우
	while (i <= m)
		tmp[ll++] = arr[i++];

	while (j <= r)
		tmp[ll++] = arr[j++];

	//tmp를 다시 arr에 복사한다.
	for (int i = l; i <= r; i++)
	{
		arr[i] = tmp[i];
	}
}
void MergeSort(int arr[], int l, int r)
{
	Divide(arr, l, r);
}
int main()
{
	int arr[MAX] = { 3,5,6,1,2,4,0,9,7,8 };

	MergeSort(arr, 0, MAX - 1);

	for (int i = 0; i < MAX; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;

	return 0;
}