정렬 알고리즘 :: 합병정렬(Merge Sort)

합병 정렬 Merge sort

 

 

기업의 인수합병(M&A; Mergers & Acquisitions)에서의 합병처럼, 나눠져있는 둘 이상을 합쳐 하나로 만드는 것이 합병 정렬이다.

 

이는 분할(Divide)과 정복(Conquer)을 반복 수행하여 데이터를 정렬하는 방식이며, 합병 정렬 또는 병합 정렬이라고도 하고, 영문 그대로 머지소트라고도 한다.

이는 데이터 열을 반씩 쪼개고 쪼갠 후(분할; divide), 더 이상 나누어지지지 않을 때 정렬하면서 다시 합치게(정복; conquer) 된다.

 

---

~ 광고 타임 ~

---

 

과정

예를 들어, 배열 { 5, 1, 7, 10, 3}이 있다고 생각해보자.

 

5

1

7

10

3

 

중간값은 7이므로 이를 기준으로 좌,우 분할한다.

 

 

 

5

1

7

10

3

 

좌측 배열 { 5, 1, 7 }과 우측 배열 { 10, 3 }으로 분할된다.

이를 다시 재귀호출(Recursive call)하여 다시 좌측 배열 { 5, 1, 7 }을 가운데 원소값 1을 기준으로 나눈다.

 

 

---

~ 광고 타임 ~

---

 

 

 

5

1

7

 

원소가 더이상 쪼개질 수 없는 조건이 되었으므로 분할을 멈춘다.

이제 두 값을 비교하여 새로운 메모리 공간(임시 배열 메모리)에 순서대로 저장한다.

 

1

5

 

 

앞서 분할했던 배열도 마찬가지로 정렬하여 병합(정복)한다.

 

1

5

7

 

이는 임시 배열이므로, 기존 배열로 값을 저장한다.

나머지 우측 배열 {10, 3 } 또한 임시배열 공간을 활용하여 위 과정을 반복함으로써 정렬을 마친다.

 

1

3

5

7

10

 

 

 

---

~ 광고 타임 ~

---

 

 

 

JAVA 코드

package tisory.blog.it_ing;

import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		System.out.println(" == 아이티-잉 정렬 알고리즘 == \n");
		int[] arr = {5, 1, 7, 10, 3};
		int len = arr.length;
		int[] tmpArr = new int[len]; //병합용 임시 배열

		System.out.println("#5. 합병정렬");
		System.out.println("Input : " + Arrays.toString(arr));
		fn_divide(0, len-1, arr, tmpArr);
		System.out.println("Result : " + Arrays.toString(arr));
	}
	//분할 함수
	public static void fn_divide(int left, int right, int[] arr, int[] tmpArr){
		if(left == right){ return; } //쪼개지지 않으면 리턴
		else{
			int mid = (left+right)/2; //중간값 찾기
			fn_divide(left, mid, arr, tmpArr); //중간 기준 좌측 배열 분할 
			fn_divide(mid+1, right, arr, tmpArr); //중간 기준 우측 배열 분할
			fn_conquer(left, mid, right, arr, tmpArr); //병합(정복)
		}
	}
	//병합(정복) 함수
	public static void fn_conquer(int left, int mid, int right, int[] arr, int[] tmpArr){
		int lIdx=left, rIdx=mid+1, tmpIdx=0, size=right-left+1;
		
		while(lIdx <= mid && rIdx <= right){
			//좌측과 우측값 비교후 순서에 맞게 임시 배열에 저장
			if(arr[lIdx] <= arr[rIdx]) { tmpArr[tmpIdx++] = arr[lIdx++]; }
			else { tmpArr[tmpIdx++] = arr[rIdx++]; }
		}
		
		//나머지 정리안된 값 저장
		while(lIdx <= mid){ tmpArr[tmpIdx++] = arr[lIdx++]; }
		while(rIdx <= right){ tmpArr[tmpIdx++] = arr[rIdx++]; }
		
		System.out.println("tmpArr : " + Arrays.toString(tmpArr));
		//기존 배열에 임시배열을 저장
		for(int i=0; i<size; i++){ arr[left+i] = tmpArr[i]; }
	}
}

 

결과

 

 

 

 

 

 

C/C++ 코드

 

#include <stdio.h>
#define ARRAY_MAX 5

//임시로 작성한 출력 함수
void printArr(int *arr){
	int i=0;
	for(i=0; i<ARRAY_MAX; i++){
		printf(" %d", arr[i]);
	}
	printf("\n");
}
//합병정렬 정복함수
void fn_conquer(int left, int mid, int right, int* arr, int* tmpArr){
	int lIdx=left, rIdx=mid+1, tmpIdx=0, size=right-left+1, i=0;

	while(lIdx <= mid && rIdx <= right){
		if(arr[lIdx] <= arr[rIdx]){ tmpArr[tmpIdx++] = arr[lIdx++]; }
		else{ tmpArr[tmpIdx++] = arr[rIdx++]; }
	}

	while(lIdx <= mid){ tmpArr[tmpIdx++] = arr[lIdx++]; }
	while(rIdx <= right){ tmpArr[tmpIdx++] = arr[rIdx++]; }

	printf("tmpArr : ");
	printArr(tmpArr);

	for(i=0; i<size; i++){ arr[left+i] = tmpArr[i]; }
}

//합병정렬 분할함수
void fn_divide(int left, int right, int* arr, int* tmpArr){
	if(left == right){ return; }
	else{
		int mid = (left+right)/2;
		fn_divide(left, mid, arr, tmpArr);
		fn_divide(mid+1, right, arr, tmpArr);
		fn_conquer(left, mid, right, arr, tmpArr);
	}
}

int main(void){
	int arr[ARRAY_MAX] = {5, 1, 7, 10, 3};
	int tmpArr[ARRAY_MAX] = {0, };

	printf("#5. 합병정렬\ninput :");
	printArr(arr);
	//합병정렬 재귀 함수 호출
	fn_divide(0, ARRAY_MAX-1, arr, tmpArr);

	printf("Result :");
	printArr(arr);

	return 0;
}

 

 

결과

 

 

 

 

 

끝.