[알고리즘]합병 정렬(merge sort).

합병 정렬은 분할 정복이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬방법이다.

이 과정을 3가지 과정으로 나누어서 보면

 

1. 분할: n개의 데이터를 더이상 쪼갤 수 없을 때까지 분할한다.

2. 정복: 분할된 문제를 해결한다.(정렬)

3. 결합: 분할해서 해결한 결과를 결합한다.

이렇게 나눌 수 있다.

 

이번 시간에는 정수의 오름차순을 기준으로 하여 합병 정렬을 설명하겠다.

 

먼저 이해를 돕기 위해서 아래 그림을 참고해라.

이 과정을 코드로 나태내기 위해서는 분할을 담당하는 함수, 정복 및 병합을 담당하는 함수 2가지가 필요하다.

먼저 분할을 담당하는 함수를 살펴보자.

void mergeSort(int arr[], int first, int last)
{
	int mid;

	if (first < last) //분할할 수 있으면
	{
		mid = (first + last) / 2; //중간지점을 계산.
		
		//둘로 나눠서 각각을 정렬.
		mergeSort(arr, first, mid); 
		mergeSort(arr, mid + 1, last);
        
        //정렬된 두 배열을 병합(자세한 설명은 다음 코드로)
		merge(arr, first, mid, last);
	}
}

다음으로 정복 및 병합을 담당하는 함수를 살펴보자.

 

분할된 배열을 효율적으로 정렬하기 위해서는 또 다른 배열이 필요하기에 동적할당을 하여 배열을 만들었다. 

void merge(int arr[], int first, int mid, int last) //정복 및 결합
{
	int* tArr = (int*)malloc(sizeof(int) * (last + 1));
	int left = first;
	int right = mid + 1;
	int tIdx = first; //배열의 시작부분
	while (left <= mid && right <= last) //left가 mid를 넘어서거나 right가 last를 넘어설 때까지 반복.
	{
		if (arr[left] > arr[right])
		{
			tArr[tIdx] = arr[right++];
		}
		else
		{
			tArr[tIdx] = arr[left++];
		}
		tIdx++;
	}

	if (left > mid)  //왼쪽 배열을 다 썻으면
	{
		while (right <= last) //오른쪽의 나머지 배열을 삽입.
		{
			tArr[tIdx] = arr[right++];
			tIdx++;
		}
	}
	else 
	{
		while (left <= mid)
		{
			tArr[tIdx] = arr[left++];
			tIdx++;
		}
	}

	//tArr에 정렬된 배열을 arr에 삽입.
	for (int i = first; i <= last; i++)
	{
		arr[i] = tArr[i];
	}
	//동적할당 해제
	free(tArr);

}

 

전체 코드

#include <stdio.h>
#include <stdlib.h>


void merge(int arr[], int first, int mid, int last) 
{
	int* tArr = (int*)malloc(sizeof(int) * (last + 1));
	int left = first;
	int right = mid + 1;
	int tIdx = first;
	while (left <= mid && right <= last) 
	{
		if (arr[left] > arr[right])
		{
			tArr[tIdx] = arr[right++];
		}
		else
		{
			tArr[tIdx] = arr[left++];
		}
		tIdx++;
	}

	if (left > mid) 
	{
		while (right <= last)
		{
			tArr[tIdx] = arr[right++];
			tIdx++;
		}
	}
	else
	{
		while (left <= mid)
		{
			tArr[tIdx] = arr[left++];
			tIdx++;
		}
	}

	for (int i = first; i <= last; i++)
	{
		arr[i] = tArr[i];
	}

	free(tArr);

}



void mergeSort(int arr[], int first, int last)
{
	int mid;

	if (first < last)
	{
		mid = (first + last) / 2;

		mergeSort(arr, first, mid);
		mergeSort(arr, mid + 1, last);
		merge(arr, first, mid, last);
	}
}


int main(void)
{
	int arr[] = { 8, 5, 1, 3, 7, 2, 6, 9 };
	mergeSort(arr, 0, 7);

	for (int i = 0; i < 8; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}