[알고리즘] 병합정렬

목표

• 고급 정렬 알고리즘 중 병합 정렬 알고리즘에 대해 이해한다.
• 고급 정렬 알고리즘 중 병합 정렬 알고리즘을 c++로 구현한다.

병합 정렬 알고리즘이란?

• 병합 : 병합하다. 합쳐지다는 의미를 가진다.
• 정렬 :  항목들을 체계적으로 정리하는 과정
• 어떠한 자료구조를 합쳐서 정렬하는 방법 
  • 분할 정복 알고리즘의 하나이다

병합 정렬 알고리즘의 순서

1. 분할 : 입력을 반으로 나눈다. 
2. 정복 : 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다.
3. 결합 : 정렬된 두 부분을 병합하여 정렬한다.

병합 정렬의 예

• 병합하는 과정

• 결합하는 구체적인 과정

병합 정렬 c++ 코드

#include <iostream>
#define MAX 8
using namespace std;

int sort[MAX];
void mergin(int ary[], int left, int mid, int right){
	int i,j,k,l;
	i = left;
	j = mid+1;
	k = left; 
	
	while( i <= mid && j <= right){
		if( ary[i] < ary[j] )
			sort[k++] = ary[i++];
		else 
			sort[k++] = ary[j++];
	}
	
	if( i > mid ){
		for(l=j ; j <=right ;j++){
			sort[k++] = ary[j]++;
		}
	}
	else {
		for(l=i ; i <=mid ;i++){
			sort[k++] = ary[i]++;
		}
	}
	for(i=left ; i <=right; i++){
		ary[i] = sort[i];
	}
}

void mergin_sort(int ary[], int left, int right){
	int mid;
	if( left < right ){
		mid = (left + right)/2;
		mergin_sort(ary, left, mid);
		mergin_sort(ary, mid+1, right);
		mergin(ary, left, mid, right);
	}
}

int main (){
	int list[MAX] = { 8, 4, 5, 1, 6, 9, 2, 3};
	mergin_sort(list, 0, 7);
	for(int i = 0 ; i < 8; i ++){
		printf("%d \n", list[i]);
	}
}

정리 및 느낀 점

• 분할 정복 알고리즘 중 하나인 병합 정렬을 이용해 정렬을 해보았다.
• 복잡하지만 효율적인 방법이다.

참조

• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html