정렬알고리즘_병합정렬 [5/8]

[ 병합 정렬이란? ]

• 퀵정렬이 이미 정렬이 완료돼있는 경우 최악 시간 복잡도 O(n^2)을 가지는 문제를 보완
• 인접한 숫자 2개를 정렬하고 인접한 정렬 묶음을 다시 정렬하는 방식을 반복 수행
• 이미 정렬된 소그룹을 계속해서 합쳐 나가는 방식으로 O(n*logN)의 시간 복잡도를 보장
• 평균적으로는 퀵정렬과 비슷한 속도이지만 어느 상황에서나 속도를 보장할 수 있다는 장점

 

---

 

코드로 구성해보겠습니다. 반복문이 여러번 중복으로 들어가서 머릿속에서 그리는데 좀 어려웠습니다. 천재가 되고 싶다...

​

병합정렬은 분할정복(퀵정렬처럼 분할해서 정렬) + 삽입정렬을 섞어쓰는 느낌입니다. 그룹을 잘게 쪼개서 시간 복잡도를 log지수로 만들고, 각 그룹을 정렬하는 방식입니다. 삽입정렬에서 설명드렸듯이 정렬이 많이 되어 있는 경우에는 삽입정렬이 가장 빠르다는 특성을 이용해, 이미 정렬되어 있는 작은 그룹들을 삽입정렬해줌으로써 정렬 횟수 증가를 log지수로 만들어버리는거죠. 대충 수행 갯수가 늘어나는게 곱하기가 아닌 더하기로 늘어나는 것을 log지수 증가로 이해하면 될 것 같습니다(문송합니다...).

​

숫자가 완전 정렬돼있는 상태라면 순수한 삽입정렬에 비해 느릴 수 있지만 그 경우에도 다른 정렬에 비해 빠르기 때문에 어떠한 경우에도 평균적으로 가장 낮은 시간 복잡도(O(n*logN))를 가진다고 볼 수 있겠네요. 코드 구성은 퀵정렬에 비해 매우 수월한 편이었습니다.

#include <stdio.h>
void swap(int* arr, int x, int y);
void complex_arrange(int* arr, int size);

void main()
{
	int arr[] = { 9, 8, 2, 10, 15, 12, 3, 22, 0, 3, 1, 1 };
	int size = sizeof(arr) / sizeof(int);
	/* 배열 출력 */
	printf("\n 정렬 전 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);

	/* 정렬 */
	complex_arrange(arr, size);

	/* 배열 출력 */
	printf("\n 정렬 후 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
}


void complex_arrange(int* arr, int size)
{
	
	// 2개짜리, 4개짜리, 8개짜리...
	int i = 2;
	while (1)
	{
		// 전체범위(j-i) ~ (j-1), 대상범위(j-i/2)~(j-1) -> 삽입정렬 수행
		for (int j = 0; j <= size; j += i)
		{
			/* 삽입정렬을 수행할 대상 */
			for (int w = j - i / 2; w < j && w > 0; w++)
			{
				/* arr[w]를 arr[j-i]까지 삽입정렬 수행 */
				int k = w;
				while (k > 0 && k > j - i && arr[k] < arr[k - 1])
				{
					swap(arr, k, k - 1);
					k--;
				}
			}
		}

		/* 남은 숫자 처리하고 반복문 탈출 */
		if (i * 2 > size)
		{
			for (i; i < size; ++i)
			{
				int k = i;
				while (k > 0 && arr[k] < arr[k - 1])
				{
					swap(arr, k, k - 1);
					k--;
				}
			}
			break;
		}
		i *= 2;
	}
}


void swap(int* arr, int x, int y)
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}

그럼 이번에도 강의에서는 어떻게 푸는지 확인해볼게요.

유투브 '동빈나'님의 알고리즘 강의를 참고하고 있습니다.

 

 

---

 

음 제 예상과는 완전히 다르게 강의에서는 재귀함수를 통해 쪼개고 새로운 배열을 임시로 생성해서 정렬, 병합하는 방식을 사용하네요. 빠르지만 계속 기존 데이터를 담을 추가 배열 공간을 생성해서 메모리 활용이 비효율적이라는 문제가 있다고 되어 있는데 제가 짠 코드는 인덱스만 활용해서 같은 효과를 내고 있어서 메모리 효율 문제는 딱히 없어보입니다.

​

그렇다면 같은 배열의 정렬에서 해당 방식과 제 방식이 횟수 차이가 날 수 있다는 말이겠네요. 전문가분들이 저렇게 짜고 있는걸보면.. 일단 강의 방식으로 한번 짜보고 수행 횟수가 얼마나 되는지 비교를 한 번 해보겠습니다. 아래는 강의에 나온 방식입니다. 로직 상 굳이 중복작동될 필요가 없는 부분만 약간 수정했습니다.

 

1. 분할함수를 통해 배열을 반으로 분할함
2. 첫번 째 분할값 기준 왼쪽 오른쪽 영역을 재귀함수의 argument로 던져줘서 동일 로직 수행
3. 더 이상 분할할게 없으면(값이 한개이면) 함수 return
4. 쪼개진 범위에서 정렬 수행

 

재귀함수는 어렵긴 한데 굳이 한 단계씩 파고들기보다는, 가장 처음과 제일 끝의 로직만 염두하면서 작성하면 생각보다 쉽게 짤 수 있습니다. 가장 처음 반으로 나눈 다음 어떻게 할 것인지 로직만 짜고 안에 범위를 던져주는 재귀함수를 호출하면 알아서 잘 작동합니다. 그리고 제일 끝에 도달했을 때는 미묘하게 오류가 날 수 있기 때문에 디버깅을 하거나 로직을 상상하면서 미세한 부분만 조정작업을 해주면 됩니다. 전체 범위에서 부분 범위별로 같은 작업을 수행할 때 재귀함수가 효율적이네요.

 

↓ 이렇게 하나씩 생각하면서 짜면 평범한 머리에서는(저같이..) 정말 답이 안나옵니다.

 

 

↓ 이렇게 생각하고 짜니 처음 반으로 쪼갤때와 마지막에 가서 어떻게 리턴할지만 잘 처리해주면 의외로 어렵지 않게 짤 수가 있습니다. 재귀함수 사용도 경험치가 중요한 것 같네요. 계속 사용하다보면 노하우가 쌓일 듯 합니다. 주로 범위가 달라지는 반복 수행문에 잘 사용 되는 것도 같구요.

 

 

범위를 재귀함수로 쪼갠 뒤에는 아래의 로직을 반복 수행해 정렬해줍니다. 원본 배열과 동일한 크기의 sorted라는 배열을 새로 만들어줘야하고, sorted에 복사했다가 원본에 복사했다가 하는 작업들이 발생해서 약간은 비효율적으로 보여지기도 합니다.

​

그리고 재귀함수로 반복하기 때문에 임시 배열인 sorted 또한 전역변수로 지정하거나 포인터를 써서 argument로 넘겨줘야 합니다. 실제 프로그램에서 사용한다면 동적할당으로 잡아서 포인터를 넘겨주고 정렬 이후에 free 시켜주는 방식으로 가면 되겠네요.

 

#include <stdio.h>
int number = 8;

int size;
int sorted[8];
int count = 0;

void merge(int a[], int m, int middle, int n)
{
	int i = m;
	int j = middle + 1;
	int k = m;
	// 작은 순서대로 배열에 삽입
	while (i <= middle && j <= n)
	{
		if (a[i] <= a[j])
			sorted[k] = a[i++];
		else
			sorted[k] = a[j++];
		k++;
	}
	// 남은 데이터 삽입
	if (i > middle)
		for (int t = j; t <= n; t++)
			sorted[k++] = a[t];

	else 
		for (int t = i; t <= middle; t++)
			sorted[k++] = a[t];
}

void mergeSort(int a[], int m, int n)
{
	// 이외의 경우는 크기가 1개인 경우
	if (m < n)
	{
		int middle = (m + n) / 2;
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

void main()
{
	int array[8] = { 7,6,5,8,3,5,9,1 };
	/* 배열 출력 */
	printf("\n   정렬 전 : ");
		for (int i = 0; i < number; i++)
			printf("%d ", array[i]);

	/* 정렬 */
	mergeSort(array, 0, number - 1);
	// 정렬된 배열을 삽입
	for (int t = 0; t < number; t++)
		array[t] = sorted[t];
	
	/* 배열 출력 */
	printf("\n   정렬 후 : ");
	for (int i = 0; i < number; i++)
		printf("%d ", array[i]);
	
}

 

---

 

이번 경우는 제 코드와 모범답안 중 어떤게 더 나은지 솔직히 잘 모르겠네요. 무조건 답안이 낫다고 하기에는 이번엔 뭔가 찝찝한 부분도 좀 있기도 하고 제 스타일도 아니긴 하고 해서..ㅎㅎ 일단 모든 수행과정에 count++을 걸어서 수행횟수를 측정해봤습니다.

↓ 자체 코드

 

↓ 강의 코드

 

일단 샘플로 넣어본 배열에서는 위와 같은 결과가 나왔습니다. 제 예상과는 다르게 swap을 한번 할 때 연산횟수가 3번이어서 강의 코드와 수행횟수 차이가 많이 나네요. 메모리 공간은 사실 동적할당해서 잠시 쓰고 버리면 되기에.. 강의 코드에 한표를 던지며 이번글은 마무리를 하겠습니다. ㅎㅎ