[정렬] MergeSort 병합정렬

약 14개월 전에 공부했던 자료구조를 다시 꺼내 공부 중에 대부분 까먹은지라.. 그때 공부했던대로 규칙만 따로 적어놓고 그려가며 떠올려봤다.

 

※ 복습용으로 작성했습니다.

※ 내용적인 면이 기억에 의존하다보니 부정확 할 가능성이 있습니다. 자세하고 정확한 이론과 풀이 방식은 시중에 파는 책이나 다른 블로그 가시는게 좋습니다.

※ 참고용으로만 보시길 바랍니다.

 

당시에 공부했던 노트인데 이론적인 부분은 쏙 빼고 순전히 조금 더 쉽게 이해하기 위해 끄적인 그림노트에 가깝다.

 

왼쪽 페이지보다 오른쪽 페이지가 더 간단한데

병합정렬의 자세한 이론적인 부분은 시중에 나온 책이나 다른 블로그에서 찾아보는걸로 하고

간단히 말하자면 병합정렬의 시간 복잡도는 O(n log n)인데, 이를 보고서 진행이 됨에 따라 절반씩 줄어든다는걸 알 수 있다.

 

오른쪽 페이지의 순서는 이러하다.

1. 배열이 1이 될때까지 잘게 나눈다.

2. 잘게 나눈 수를 가까운 배열의 수와 비교해서 정렬한다.

3. 정렬한 덩어리들을 또 비교해서 정렬한다.

 

대충 이러한데 좀 더 쉽게 설명하면,

1 6 2 9 4 8 5 3 7 이라는 9개의 수로 배열을 만들었다 가정할 때,

처음엔  1 6 2 9 | 4 8 5 3 7 로 나누고,

이를 또 1 6 | 2 9 | 4 8 | 5 3 7 로 나누고,

또 잘게 나눈 후 비교한다.

 

빨간색으로 숫자가 써있는건 병합정렬의 진행 순서로 마지막에 나오는 코드를 천천히 뜯어보면 저 순서로 돌아간다.

 

 

이곳도 오른쪽 페이지를 보면 좀 더 쉬운데

아무래도 반복적으로 나눈 후 병합을 진행하다보니 보통 재귀적으로 짜는갑다. 하고 배웠다.

때문에 병함 정렬 함수에 인자로 배열과 배열크기 그리고 임시로 수를 담을 임시배열이면 된다.

 

재귀함수를 왼쪽/오른쪽 나누어 차례대로 잘게 쪼갠 다음

탈출조건을 만족하면, 함수에서 차례대로 빠져나오며 정렬되는 방식이다.

 

이 노트는 오늘 14개월전 노트를 보고 다시 생각하고 그려놓은것이다.

어느분께 배운 방식인데 특히나 재귀함수 코드를 짤 때 하나하나 그려가면서 생각하면 매우 간편하다.

 

 

 

아래는 백준알고리즘 2751번 정답 코드이다.

배운 방식 그대로 떠올리며 만들었다.

 

#include <iostream>

void printArray(const int* pData, int nSize);
void mergeSort(int* pData, int nSize, int* pTemp);

int main()
{
	int nInputData = 0;
	int arData[1000000]{};
	int arTemp[1000000]{};
	int nData = 0;
	int nTemp{};
	scanf_s("%d", &nInputData);

	for (int i = 0; i < nInputData; i++)
	{
		scanf_s("%d", &nTemp);
		arData[i] = nTemp;
	}

	mergeSort(arData, nInputData, arTemp);
	printArray(arData, nInputData);
	 

}

void printArray(const int* pData, int nSize)
{
	for (int i = 0; i < nSize; i++)
	{
		printf("%d\n", pData[i]);
	}
}

void mergeSort(int* pData, int nSize, int* pTemp)
{
	if (nSize <= 1)
		return;

	int* pLeft = pData;
	int nLeftLength = nSize / 2;
	int* pRight = pData + nLeftLength;
	int nRightLength = nSize - nLeftLength;

	mergeSort(pLeft, nLeftLength, pTemp);
	mergeSort(pRight, nRightLength, pTemp);


	int* pSelectMin = nullptr;
	int* pSelectIndex = nullptr;
	int nLeftIndex{};
	int nRightIndex{};

	for (int i = 0; i < nSize; i++)
	{
		pSelectMin = pLeft + nLeftIndex;
		pSelectIndex = &nLeftIndex;

		if (nLeftIndex >= nLeftLength || nRightIndex < nRightLength && pLeft[nLeftIndex] > pRight[nRightIndex])
		{
			//오른쪽 선택했단 뜻
			pSelectMin = pRight + nRightIndex;
			pSelectIndex = &nRightIndex;
		}

		pTemp[i] = *pSelectMin;
		(*pSelectIndex)++;
	}

	for (int i = 0; i < nSize; i++)
	{
		pData[i] = pTemp[i];
	}
}

 

당시엔 정말 기계적으로 작성하기도 했고 한참 공부하던 때인지라 뇌가 말랑말랑 했었는데 다양한 인생의 쓴맛을 몰아 겪어 조울증과 공황을 겪다보니 뇌가 진짜 딱딱하게 굳은 느낌이다..

그래도 여전히 컴퓨터 공부는 재밌다!