Merge Sort

병합정렬을 구현해 보았다.

Quick 정렬과 비슷하게 분할을 통해 정렬해 나아간다. 시간복잡도는 nlogn 으로 Quick 과 비슷한 수준이다.

Quick 의 단점인 Pivot 설정에 따라 최악의 경우 O(N^2 ) 이 되는 경우가 있을 수 있었지만

Merge 의 경우 무조건 절반으로 나누기 때문에 항상 O(NlogN) 을 갖는 장점이 있다.

정렬 알고리즘 중 가장 효율적인 방법이라고 볼 수 있다.

 

단점을 보자면 아래에서 보다시피 Tempdata 라는 메모리를 할당하게 된다.

그러다 보니 매우 광범위한 data 인경우 혹은 메모리를 할당 할 수 없는 상황에서는 적합하지 않을 수 있다.

그럴 경우에는 오히려 Quick 방식이 적합할 수 있다.

 

 

아래 사진과 같이 아주 작은 요소부터 시작한다. 이는 재귀함수를 통해 구현하면 아주 짧고 쉽게 만들 수 있다.

Merge Sort 참고 자료

 

오름차 정렬로 만들었으며, 내림차로 하고 싶다면 if else 문의 내용을 서로 바꿔주기만 하면 되겠지? ㅎㅎ

#include <stdio.h>

#define DATA_SIZE 10

void __StartMerge(int data[], int p, int q, int r)
{
	int i = p, j = q + 1, k = p;
	int Tempdata[DATA_SIZE];

	while (i <= q && j <= r)
	{
		if (data[i] >= data[j])
			Tempdata[k++] = data[j++];
		else
			Tempdata[k++] = data[i++];
	}

	while (i <= q)
		Tempdata[k++] = data[i++];
	while (j <= r)
		Tempdata[k++] = data[j++];

	int t;
	for (t = p; t <= r; t++)
		data[t] = Tempdata[t];
}

void MergeSort(int data[], int p, int r)
{
	int q;

	if (p < r)
	{
		q = (int)(p + r) / 2.f;

		MergeSort(data, p, q);
		MergeSort(data, q+1, r);
		__StartMerge(data, p, q, r);
	}
}

void PrintSort(int data[], int nSize)
{
	int i;

	for (i = 0; i < nSize; i++)
	{
		printf("%3d", data[i]);
	}
	printf("\n");
}

int main(void)
{
	int data[DATA_SIZE] = { 2, 20, 40, 60, 41, 22, 8, 7, 27, 50 };

	MergeSort(data, 0, DATA_SIZE-1);
	
	PrintSort(data, DATA_SIZE);

	getchar();

	return 0;
}

Merge Sort 오름차순 결과