자바로 구현한 머지소트(merge sort, 합병정렬), 자바 소스 코드.

1. 두 배열의 합병

정렬 된 두 배열 A와 B를 생각해봅시다. 그림 1에서와 같이 정렬된 배열 A, B에 관하여 합병 할 때, 두 배열 A, B의 크기의 합과 같은 배열 C를 준비합니다. 인덱스 iA와 iB에 따라 값의 크기를 비교하고, 작은 값을 먼저 인덱스 iC가 가리키는 곳에 저장합니다. 저장한 후에는 해당하는 인덱스 값을 1씩 늘려줍니다. 그림 1에서 과정을 보여줍니다.

 

(1)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
				↑														↑
				iA														iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C
	↑
	iC

 

(2)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
						↑												↑
						iA												iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1
		↑
		iC

 

(3)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
						↑													↑
						iA													iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2
			↑
			iC

 

(4)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
								↑											↑
								iA											iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3
					↑
					iC

 

(5)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
								↑												↑
								iA												iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3		4
							↑
							iC

 

(6)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
										↑										↑
										iA										iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3		4		5
									↑
									iC

 

(7)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
												↑								↑
												iA								iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3		4		5		7
											↑
											iC

 

(8)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
														↑						↑
														iA						iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3		4		5		7		9
													↑
													iC

 

(9)	배열번호			0		1		2		3		4					배열번호	0	1	2	3
	배열 A			1		3		5		7		9					배열 B	2	4	10	12
														↑							↑
														iA							iB
배열번호	0	1	2		3		4		5		6		7		8
배열 C	1	2	3		4		5		7		9		10
															↑
															iC

 

(10)	배열번호			0		1		2		3		4						배열번호		0	1	2	3
	배열 A			1		3		5		7		9						배열 B		2	4	10	12
														↑										↑
														iA										iB
배열번호		0	1		2		3		4		5		6		7	8
배열 C		1	2		3		4		5		7		9		10	12
																	↑
																	iC

 

그림 1. 정렬된 배열 A, B를 배열 C에 합병

 

이런 과정을 그림 2에서 흐름도로 나타냈습니다.

 

그림 2. 합병 흐름도

 

이를 자바로 구현한 소스코드는 아래 그림 3과 같습니다.

 

그림 3. 합병 과정의 자바 소스

 

2. 머지소트의 구현

 

(1) 머지소트의 디자인 패턴: divide-conquer

머지소트는 divide-and-conquer라는 디자인 패턴을 따릅니다. 이 디자인 패턴은 다음 세 가지 단계를 따릅니다. 첫째, divide 단계에서 입력 값이 기준 값 보다 작거나 같으면 문제 풀이를 시작합니다. 그렇지 않다면 입력 값을 더 작은 값으로 쪼갭니다. 둘째, conquer 단계에서는 재귀적으로 더 작은 값으로 쪼개진 하위 문제를 풉니다. 셋째, combine 단계에서 합병을 통해 원래 문제를 풉니다.

 

(2) 자바로 구현한 머지소트

이 세 단계를 머지소트에 적용하면 다음 세 단계를 따릅니다.

(ㄱ) divide: 배열 S의 원소가 없거나 하나만 있다면 return 합니다. 이는 배열 S가 이미 정렬되어 있는 것으로 보기 때문입니다. 그렇지 않다면, 배열 S의 원소를 하위 배열 S1과 S2로 쪼갭니다. 이 때, 배열 S1은 배열 S의 원소를 배열의 위치로 나타냈을 때 0 ~ n/2, 배열 S2는 n/2 + 1 ~ n의 원소를 갖습니다.

(ㄴ) conquer: 재귀적으로 배열 S1, S2에 관해 divide와 정렬합니다.

(ㄷ) combine: 정렬된 S1과 S2를 합병하여 S에 저장합니다.

 

예를 들어 배열 S = { 85, 24, 63, 45, 17, 31, 96, 50 } 을 머지소트 합시다. Divide 단계에서 S는 S1 = { 85, 24, 63, 45 }, S2 = { 17, 31, 96, 50 } 으로 나뉩니다. S1은 S1-S1 = { 85, 24 }, S1-S2 = { 63, 45 } 로 나뉩니다. 트리 구조로 생각하면, 중위순회(inorder traversal, 깊이우선탐색의 한 종류: 위키피디아 링크 참고: https://en.wikipedia.org/wiki/Tree_traversal )로 divide, conquer, combine과정이 이루어집니다. 이 과정을 순차적으로 나타낸 것이 그림 4입니다. 그림 4에서 S의 하위 배열은 S1, S2로 나뉘고, S1의 하위 배열은 S1-S1, S1-S2로 나뉜다고 표현했습니다.

 

배열번호	0	1	2	3	4	5	6	7
S	85	24	63	45	17	31	96	50
배열번호	0	1	2	3
S1	85	24	63	45
배열번호	0	1	2	3
S2	17	31	96	50
배열번호	0	1
S1-S1	85	24
배열번호	0	1
S1-S2	63	45
배열번호	0
S1-S1-S1	85
배열번호	0
S1-S1-S2	24
배열번호	0	1
S1-S1	24	85
배열번호	0
S1-S2-S1	63
배열번호	0
S1-S2-S2	45
배열번호	0	1
S1-S2	45	63
배열번호	0	1	2	3
S1	24	45	63	85
배열번호	0	1
S2-S1	17	31
배열번호	0	1
S2-S2	96	50
배열번호	0
S2-S1-S1	17
배열번호	0
S2-S1-S2	31
배열번호	0	1
S2-S1	17	31
배열번호	0
S2-S2-S1	96
배열번호	0
S2-S2-S2	50
배열번호	0	1
S2-S2	50	96
배열번호	0	1	2	3
S2	17	31	50	96
배열번호	0	1	2	3	4	5	6	7
S	17	24	31	45	50	63	85	96

그림4. 배열 S가 머지소트 되는 과정

 

위 과정을 그림 5에서 자바 소스 코드로 표현했습니다.

 

그림 5. 머지소트의 자바 소스 코드

 

그림 4에서 살펴본 과정 대로 머지소트가 잘 되었는지 확인해보았습니다(그림 6 자바 콘솔의 머지소트 결과).

그림 6. 자바 콘솔의 머지소트 구현 결과

1. package merge_sort_array;
2.  
3. public class merge_sort_array {
4.  
5.         public static void print_arr (int[] arr) {
6.                 for (int i = 0; i < arr.length; i++) {
7.                         System.out.print(arr[i] + " ");
8.                 }
9.                 System.out.println();
10.         }
11.        
12.         public static void merge (int[] arrA, int[] arrB, int[] arrC) {
13.                 int iA = 0;
14.                 int iB = 0;
15.                 int iC = 0;
16.                
17.                 while (iA < arrA.length) {
18.                         if (iB < arrB.length) {
19.                                 if ( arrA[iA] < arrB[iB]) {
20.                                         arrC[iC] = arrA[iA];
21.                                         iA++;
22.                                 } else {
23.                                         arrC[iC] = arrB[iB];
24.                                         iB++;
25.                                 }
26.                                 iC++;
27.                         } else {
28.                                 while (iA < arrA.length) {
29.                                         arrC[iC] = arrA[iA];
30.                                         iA++;
31.                                         iC++;
32.                                 }
33.                         }
34.                 }
35.                
36.                 while (iB < arrB.length) {
37.                         arrC[iC] = arrB[iB];
38.                         iB++;
39.                         iC++;
40.                 }
41.         }
42.        
43.         public static void merge_sort (int[] arr) {
44.                 int n = arr.length;
45.                
46.                 if (n == 1) return;
47.                
48.                 int[] arr_temp1 = new int[n/2];
49.                 int[] arr_temp2 = new int[n - n/2];
50.                
51.                 for (int i = 0; i< n/2; i++) {
52.                         arr_temp1[i] = arr[i];
53.                 }
54.                 for (int i = 0; i< n - n/2; i++) {
55.                         arr_temp2[i] = arr[i + n/2];
56.                 }
57.                 System.out.print("Array S1: ");
58.                 print_arr(arr_temp1);
59.                 System.out.print("Array S2: ");
60.                 print_arr(arr_temp2);
61.                
62.                 merge_sort(arr_temp1);
63.                 merge_sort(arr_temp2);
64.                
65.                 merge(arr_temp1, arr_temp2, arr);
66.                 System.out.print("Array S: ");
67.                 print_arr(arr);
68.         }
69.        
70.         public static void main (String[] args) {
71.                 int[] arr = {85, 24, 63, 45, 17, 31, 96, 50};
72.                 System.out.print("정렬 전 배열: ");
73.                 print_arr(arr);
74.                 merge_sort(arr);
75.                 System.out.print("정렬된 배열: ");
76.                 print_arr(arr);
77.         }
78. }
79.  

3. 더 생각해볼 문제

   (1) 머지소트는 속도와 메모리 공간을 trade-off하여 풀이하기 때문에 문제 크기에 따라 스택오버플로우가 발생할 수 있습니다. 이를 해결하려면 어떻게 해야할까요? inplacing sort

   (2) 위 예에서 integer 형의 배열에 관해서 다루었습니다. 그런데 float 형태의 배열을 다루려면 어떻게 해야할까요? 그리고 문자열이 담긴 형태의 자료는 어떻게 정렬해야 할까요? generic. C에서 템플릿에 해당.

참고한 책

---

데이타 구조론:고급 프로그래밍.앨고리듬.화일처리

저자

강맹규 지음

출판사

홍릉과학출판사 | 1988-03-01 출간

카테고리

컴퓨터/IT

책소개

-

---

---

Data Structures and Algorithms in Java. 2/E,

저자

Goodrich, Michael T. 지음

출판사

Wiley | 2000-08-01 출간

카테고리

과학/기술

책소개

Using the power of technology to go...

---