병합정렬(Merge Sort)

전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식.

1. 분할

 아래 그림과 같이 배열 집합을 하나의 원소 단위로 각각을 분할한다.

2. 병합

  분할된 각각의 원소에 대해 서로의 쌍을 비교하여 sorting 후 병합한다.

3. Sorting 과정.

병합시의 Sorting 과정을 살펴보면 우선 병합하려고 하는 크기의 메모리를 할당한 다음, 두 개의 원소에 대해 각각을 비교하여 할당된 메모리에 집어넣는다.

그림을 보며 설명하는게 더 나을지도..

1. 0,3,8 과 1,2,4에 대한 병합 작업이 이루어지고 있다. 두 배열을 합치면 총 6의 공간이 필요하기 때문에

6의 메모리 배열을 새롭게 만들어 두고 작업을 진행한다. 각 배열의 제일 왼쪽 원소부터 서로 비교한다. 

두 개의 원소 중 작은 값을 메모리 배열에 집어넣고 메모리에 들어간 배열은 인덱스를 1증가시킨다.

위의 그림에서 보면 0이 1보다 작기 때문에 0이 메모리에 들어가고 인덱스가 하나 증가되어 3을 가리키게 되었다.

2. 3과 1을 비교한다. 1이 더 작으므로 1이 메모리에 들어가고, 인덱스는 2를 가리킨다. 2또한 3보다 작으므로 메모리에 들어가고 인덱스는 4를 가리키게 된다.

3. 이런식으로 병합할 때마다 Sorting을 하면 최종 정렬된 결과를 확인할 수 있다.

	#include <stdio.h>
	void merge_sort(int array[],int left ,int right); //분할 함수
	void merge(int num[],int left,int mid,int right); //병합 함수
	const int ITEMSIZE = 6;
	int result[ITEMSIZE];
	int main(void)
	{
	int array[ITEMSIZE] = {3, 8, 0, 2, 1, 4};
	merge_sort(array, 0, ITEMSIZE - 1);
	}
	void merge_sort(int array[], int left, int right)
	{
	int mid;
	// 분할이 다 되지 않았을 경우 if 문 실행
	if(left < right){
	mid = (left + right)/2;
	merge_sort(array, left, mid); //왼쪽 블록 분할
	merge_sort(array, mid+1, right); //오른쪽 블록 분할
	merge(array, left, mid, right); //분할된 블록 병합
	}
	void merge(int array[], int left, int mid, int right)
	{
	int i, j, k, m;
	i = left;
	j = mid + 1;
	k = left; //결과 배열의 인덱스
	int tempArray[ITEMSIZE];
	//left부터 mid 까지의 블록과 mid+1부터 right까지의 블록을 서로 비교하는 부분
	while (i <= mid && j <= right) {
	if (array[i] < array[j]){ //left index 값이 right index 값보다 작으면 left index 값을 결과 result에 복사
	tempArray[k] = array[i];
	i++;
	}else{ //아니라면 right index 값을 결과 result에 복사
	tempArray[k] = array[j];
	j++;
	}
	k++;
	}
	// left 블록의 값은 다 처리되었는데 right 블록의 index가 아직 남아있을 경우
	// right index를 순차적으로 결과 result에 복사
	if (i > mid){
	for (m = j; m <= right; m++){
	tempArray[k] = array[m];
	k++;
	}
	} else { // left 블록의 index가 아직 남아있을 경우 left index를 순차적으로 결과 result에 복사
	for (m = i; m <= mid; m++){
	tempArray[k] = array[m];
	k++;
	}
	}
	for(m = left; m <= right; m++){
	array[m] = tempArray[m];
	}
	}

view raw gistfile1.c hosted with ❤ by GitHub