병합 정렬 (merge sort) c++

배열을 오름차순 혹은 내림차순으로 정렬하는 알고리즘 중 하나이다. 버블 정렬 알고리즘보다 복잡하지만, 속도가 빠르다는 것이 장점이다.

 

1. 하나의 배열이 있을때 길이가 1이 될때까지 /2로 게속 쪼개어 준다.

2. 쪼개진  배열을 2개씩 비교 후 병합한다.

 

이론적으론 쉽지만 재귀함수를 써야하기 때문에 구현하기는 생각보다 어렵다. 밑에는 병합 정렬의 로직을 표현한 것이다.

 

 

출처 : 위키 백과

void Merge(int a[],int left, int mid , int right)
{

}

void Divide(int a[], int left, int right)
{

}

 

우선 2가지의 기능을 하는 함수가 필요하다. 배열을 쪼개어줄 분할 함수와 그걸 다시 합치면서 비교해줄 병합 함수 두가지이다.

 

void Divide(int a[], int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;

		Divide(a, left, mid);
		Divide(a, mid + 1, right);
		
		Merge(a, left, mid, right);

	}
}

배열의 길이가 1이 될때까지 나누어야 하기 때문에 조건을 left<right 걸어둔다. 이후 중간 지점인 mid를 구해 재귀함수를 돌려준다.

 

배열이 전부 나누어졌다면 더이상 재귀함수는 반복하지 않고 Merge함수 부분으로 넘어가게 된다. 그렇기 때문에 분할 후 병합하는 함수를 통해 함수가 합쳐지게 된다.

 

void Merge(int a[], int left, int mid, int right)
{
	int temp[100];

	int i = left;
	int j = mid + 1;
	int k = 0;
}

Merge 함수 부분이다 우선 정렬된 인덱스를 잠시 넣어둘 temp를 만들어준다

i 는 비교가될 두 배열중의 왼쪽을, j는 오른쪽을 맡는다.

 

while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
		{
			temp[k] = a[i];
			i++;
			k++;
		}
		else if (a[i] > a[j])
		{
			temp[k] = a[j];
			j++;
			k++;
		}
	}

i와 j의 인덱스값을 비교해 더 작은쪽을 temp에 담아주는 방식이다. 그래서 k는 temp의 위치 인덱스이다.

 

 

	while (i <= mid)
	{
		temp[k] = a[i];
		i++;
		k++;
	}

	while (j <= right)
	{
		temp[k] = a[j];
		j++;
		k++;
	}

만약 두 배열중 하나가 전부 끝낫다면 다른하나를 전부 담아주는 while문을 작성한다.

 

k--;

while (k >= 0)
{
	a[left + k] = temp[k];
	k--;
}

 

마지막으로 정렬된 배열을 실제 a배열에 담아준다. 중요한 점은 현재k가 이미 배열의 길이를 넘어섰기 때문에 한번 빼주어야 한다.

 

#include <iostream>
using namespace std;

void Merge(int a[], int left, int mid, int right)
{
	int temp[100];

	int i = left;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= right)
	{
		if (a[i] <= a[j])
		{
			temp[k] = a[i];
			i++;
			k++;
		}
		else if (a[i] > a[j])
		{
			temp[k] = a[j];
			j++;
			k++;
		}
	}

	while (i <= mid)
	{
		temp[k] = a[i];
		i++;
		k++;
	}

	while (j <= right)
	{
		temp[k] = a[j];
		j++;
		k++;
	}

	k--;

	while (k >= 0)
	{
		a[left + k] = temp[k];
		k--;
	}
}

void Divide(int a[], int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;

		Divide(a, left, mid);
		Divide(a, mid + 1, right);

		Merge(a, left, mid, right);
	}
}

int main()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int arrSize = 10;

	for (int i = 0; i < arrSize; i++)
	{
		cout << arr[i] << ", ";
	}

	cout << "\n" << endl;

	Divide(arr, 0, arrSize - 1);

	for (int i = 0; i < arrSize; i++)
	{
		cout << arr[i] << ", ";
	}
}