[자료구조]합병 정렬(merge sort)

합병 정렬

분할 정복 알고리즘의 하나로 정렬되지 않은 리스크를 절반으로 나누어 비슷한 크기의 리스트로 나눕니다.  분할된 리스트의 크기가 1이 될 때까지 반복합니다.

이렇게 분할된 리스트들을 다시 병합하여 정렬하는 방식이 합병 정렬입니다.

 

다음은 합병 정렬의 예입니다.

그림 출처 : 위키 합병정렬

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

기본 이론

합병 정렬은 길이가 비슷한 정렬이 된 두 리스크를 정렬된 하나의 리스트로 만드는 것이라고 생각하면 됩니다.

즉, {2,4,6,8} , {1,3,5,7,9}로 정렬된 두 리스트가 있습니다. 

이 두 리스트를 정렬된 하나의 리스트로 만들기 위해서는 각 리스트의 첫 번째 인자를 비교하여 작은 수를 리스트의 맨 앞에 저장합니다. 

그리고 더 작은 수를 가지고 있던 리스트의 값을 다음 값으로 이동합니다.

이를 반복하여 정렬합니다.

 

그림으로 보면 다음과 같습니다.

 

 

 

<Code1>

반복을 통해 두 리스트를 비교하여 작은 값을 리스트에 추가합니다. 

두 리스트의 index가 모두 길이보다 작을 때 반복을 수행하며 반복이 끝나면 아직 리스트에 추가되지 못한 값을 반복을 통해 추가합니다.

 

코드는 정상작동하지만 빨간 동그라미처럼 비슷하면서 공통적인 부분이 4번이나 반복됩니다.

이를 하나로 통합하도록 합시다.

 

<Code2>

int main()
{
	int arData[9] = { 2,4,6,8, 1,3,5,7,9, };
	int arTmp[9] = {};
	int nLength = 0;
	int *pLeftData = nullptr;
	int *pRightData = nullptr;
	int nLeftLength = 0;
	int nRightLength = 0;
	int nLeftIdx = 0;
	int nRightIdx = 0;
	int nIndex = 0;

	nLength = 9;
	pLeftData = arData;
	nLeftLength = nLength / 2;
	pRightData = arData + nLeftLength;
	nRightLength = nLength - nLeftLength;

	for (int i = 0; i < nLength; i++) {
		int *pSelectData = pLeftData;
		int *pSelectIdx = &nLeftIdx;
		if (nLeftIdx >= nLeftLength ||
			(nRightIdx < nRightLength && pLeftData[nLeftIdx] > pRightData[nRightIdx]) )
		{
			pSelectData = pRightData;
			pSelectIdx = &nRightIdx;
		}
		arTmp[i] = pSelectData[*pSelectIdx];
		(*pSelectIdx)++;
	}

	for (int i = 0; i < nLength; i++) {
		arData[i] = arTmp[i];
	}

	printData(arData, nLength);
	return 0;
}

위 코드에서 default를 left로 한 다음 right인 경우에 변경하는 식의 코드를 구성했습니다. 이를 통해서 처음 코드의 반복된 부분을 하나로 통합하였습니다. 

 

****

위 방식처럼 2개를 비교하는 경우 하나를 default로 한 다음 아닌 경우 다른 하나로 값을 변경하는 식의 코드 구성을 하는 것이 좋습니다.

****

 

지금까지는 이미 정렬된 비슷한 크기의 리스트를 합병하여 정렬하는 방식이었고, 마지막으로 정렬되지 않은 리스트를 합병 정렬의 방법으로 정렬하는 Code를 보겠습니다.

 

<Merge Sort Code>

void mergeSort(int * pData, int nLength, int * pTmp)
{
	if (nLength <= 1)
		return;

	int *pLeftData = nullptr;
	int *pRightData = nullptr;
	int nLeftLength = 0;
	int nRightLength = 0;
	int nLeftIdx = 0;
	int nRightIdx = 0;
	int nIndex = 0;

	pLeftData = pData;
	nLeftLength = nLength / 2;
	pRightData = pData + nLeftLength;
	nRightLength = nLength - nLeftLength;

	mergeSort(pLeftData, nLeftLength, pTmp);
	mergeSort(pRightData, nRightLength, pTmp);

	for (int i = 0; i < nLength; i++) {
		int *pSelectData = pLeftData;
		int *pSelectIdx = &nLeftIdx;
		if (nLeftIdx >= nLeftLength ||
			(nRightIdx < nRightLength && pLeftData[nLeftIdx] > pRightData[nRightIdx]))
		{
			pSelectData = pRightData;
			pSelectIdx = &nRightIdx;
		}
		pTmp[i] = pSelectData[*pSelectIdx];
		(*pSelectIdx)++;
	}

	for (int i = 0; i < nLength; i++) {
		pData[i] = pTmp[i];
	}
}

위 코드가 재귀적인 방식을 통해 합병 정렬을 하는 코드입니다. 

함수에 정렬할 리스트의 배열을 받으면 이 리스트를 반으로 나누어 비슷한 크기의 리스트로 나눕니다. 

이를 크기가 1이 될 때까지 반복하기 위해 코드의 파란색 부분처럼 자기 자식을 다시 호출하는 재귀함수의 방식을 사용합니다. 

크기가 1이 되면 정렬을 시작합니다.

 

****

합병 정렬을 함수로 만드는 경우 정렬하고자 하는 리스트의 배열은 데이터 전달의 목적과 데이터를 받아올 목적 2개를 동시에 가진다. 

즉, in 파라미터와 out 파라미터의 2개의 성질을 동시에 가지게 된다.

****