병합 정렬(Merge Sort)

병합정렬은 두 개 배열을 각각 정렬 후 처음부터(혹은 끝부터) 서로 비교하며 합치기를 반복하여 정렬하는 방식이다.

 

예를 들면 

 

배열 int a = {4, 1, 3, 2};

배열 int b = {7, 1, 5, 3};

 

두개의 배열이 존재할 때,

1.a와 b를 각각 내림차순 혹은 오름차순으로 원하는 방식대로 정렬해준다.

결과 :  a = {1, 2, 3, 4};  b = {1, 3, 5, 7};

 

2.a와 b 의 인덱스를 가리키는 변수를 각각 둔다.

int pa = 0, pb = 0;

 

3.pa와 pb가 각각의 배열의 마지막을 가리킬 때까지 반복해서 a[pa] 와 b[pb]를 비교해서 배열 a+b의 크기를 가진 배열 c에 복사해준다.

 

while(pa<배열 a의 마지막 인덱스 && pb< 배열 b의 마지막 인덱스)

{

//a와 b 비교 후

if(a[pa]>b[pb]) //더 작은 값을 먼저 복사해준다.

   c[pc++] = a[pb++];

else

   c[pc++] = b[pa++];

}

//위의 반복문에서 pa나 pb 중 마지막 인덱스에 먼저 도착할 경우 나머지는 해당 인덱스부터 마지막까지 정렬된 순서대로 복사해주며 정렬을 끝낸다. 

while(pa<배열 a의 마지막 인덱스)

{

  c[pc++] = a[pa++];
}

while(pb<배열 b의 마지막 인덱스)

{

  c[pc++] = a[pb++];
}

 

이런식으로 배열 2개를 비교하며 병합해준다. 

 

우리가 흔히 알고 있는 병합 배열은 배열 1개부터 시작해서 2개씩 병합 후 4개씩 병합 과 같은식으로 분할 정복하여 이뤄지는데 기본적으로는 위의 방식을 반복해서 병합정렬을 구현할 수 있다.

 

#include<iostream>
#define SIZE_OF_A 3
#define SIZE_OF_B 3

int main(void)
{
	int a[SIZE_OF_A] = {1,2,3};
	int b[SIZE_OF_B] = {2,5,6};
	int buff[SIZE_OF_A + SIZE_OF_B] = {0,};

	int pa = 0, pb = 0, pBuff = 0;

	while (pa < SIZE_OF_A && pb < SIZE_OF_B)
	{
		if (a[pa] > b[pb])
			buff[pBuff++] = b[pb++];
		else
			buff[pBuff++] = a[pa++];
		//복사 배열 확인
		for (int i = 0; i < SIZE_OF_A + SIZE_OF_B; ++i)
		{
			std::cout << buff[i] << " ";
		}
		std::cout << std::endl;
	}
	while (pa < SIZE_OF_A)
	{
		buff[pBuff++] = a[pa++];
		//복사 배열 확인
		for (int i = 0; i < SIZE_OF_A + SIZE_OF_B; ++i)
		{
			std::cout << buff[i] << " ";
		}
		std::cout << std::endl;
	}
	while (pb < SIZE_OF_B)
	{
		buff[pBuff++] = b[pb++];
		//복사 배열 확인
		for (int i = 0; i < SIZE_OF_A + SIZE_OF_B; ++i)
		{
			std::cout << buff[i] << " ";
		}
		std::cout << std::endl;
	}

}

 

이를 응용하여 뒤죽박죽인 배열 한개를 반으로 쪼개고 쪼개고 해서 병합정렬을 만들 수도 있다.