1. 두 배열의 합병

정렬 된 두 배열 A B를 생각해봅시다. 그림 1에서와 같이 정렬된 배열 A, B에 관하여 합병 할 때, 두 배열 A, B의 크기의 합과 같은 배열 C를 준비합니다. 인덱스 iAiB에 따라 값의 크기를 비교하고, 작은 값을 먼저 인덱스 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의 원소를 하위 배열 S1S2로 쪼갭니다. 이 때, 배열 S1은 배열 S의 원소를 배열의 위치로 나타냈을 때 0 ~ n/2, 배열 S2n/2 + 1 ~ n의 원소를 갖습니다.

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

() combine: 정렬된 S1S2를 합병하여 S에 저장합니다.

 

예를 들어 배열 S = { 85, 24, 63, 45, 17, 31, 96, 50 } 을 머지소트 합시다. Divide 단계에서 SS1 = { 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에서 템플릿에 해당.


참고한 책





Data Structures and Algorithms in Java. 2/E,

저자
Goodrich, Michael T. 지음
출판사
Wiley | 2000-08-01 출간
카테고리
과학/기술
책소개
Using the power of technology to go...
가격비교



신고
Posted by 공돌이pooh

댓글을 달아 주세요

  1. 좋은 글 2016.03.21 23:50 신고  댓글주소  수정/삭제  댓글쓰기

    소스가 큰 도움이 되었습니다
    감사합니다

  2. kalin 2016.08.09 16:10 신고  댓글주소  수정/삭제  댓글쓰기

    공부하는중에 참고합니다. 감사합니다.

  3. lee 2016.10.09 03:06 신고  댓글주소  수정/삭제  댓글쓰기

    혹시 저 런의 크기를 3레코드로 바꿔줄려면 어떻게 해야되나요???

  4. good 2016.10.09 03:10 신고  댓글주소  수정/삭제  댓글쓰기

    혹시 2원행렬병합은 어떻게 해야되는지 알 수 있을까요
    화일 수가 15개이고 런의 크기는 3레코드로 총 5개의 런으로 하는 병합입니다.

  5. Favicon of http://woongheelee.com BlogIcon 공돌이pooh 2016.10.09 04:31 신고  댓글주소  수정/삭제  댓글쓰기

    윗 두분이 같은 문제를 물어보시는 것 같은데, 어떤건지 보여주시면 연구해볼게요.

  6. good 2016.10.09 11:29 신고  댓글주소  수정/삭제  댓글쓰기

    정렬할 화일이
    50 110 95 15 100 30 150 40 120 60 70 130 20 140 80 인데,
    런의크기를 3레코드로 해서 5개의 런으로 만든뒤에 2원합병 하는 것입니다.
    50 110 95 / 15 30 100/ ..... 이런식입니다

    c++ 언어는 소스가 많은데 자바는 하나도 없더라구요

    • Favicon of http://woongheelee.com BlogIcon 공돌이pooh 2016.10.09 21:03 신고  댓글주소  수정/삭제

      Divide로 쪼갰을 때 가장 작은 원소 개수가 세 개가 되나요? 정렬할 원소의 개수가 몇 개 안되는데, 공책에 손으로 직접 알고리즘 과정 하나씩 연습해보고 구현해보세요.

  7. 질문이요 2017.07.04 21:14 신고  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. 좋은 글 감사합니다.
    궁금한게 있습니다.
    merge_sort(arr_temp1);
    merge_sort(arr_temp2);

    //여기서 arr을 출력해주면 병합정렬이 되지 않은 상태로 출력이 되는건 이해가 갑니다.

    merge(arr_temp1, arr_temp2, arr);

    //궁금한 것은 여기 부분입니다. merge() 메소드는 void여서 return이 없습니다. 하지만 merge() 이후에 arr을 출력할 경우, 정렬이 되어서 출력이 됩니다. 왜 이렇게 나오는거죠?

    • Favicon of http://woongheelee.com BlogIcon 공돌이pooh 2017.07.04 22:30 신고  댓글주소  수정/삭제

      배열 이름을 함수 인자로 넣으면, 배열의 주소가 들어간다고 생각하시면 됩니다.

      그래서 함수 내에서 배열에 뭔가 변화를 주면 그 배열 자체가 변하는 것이죠.

      그래서 마지막에 배열을 출력해보면, 정렬된 배열이 나타나게 됩니다.

  8. 질문이용 2017.10.11 20:32 신고  댓글주소  수정/삭제  댓글쓰기

    결과 값이 출력될 때, Array를 S3까지 나눠서 출력하기 위해서는 어떻게 해야하는지 알 수 있을까요?

  9. 감사합니다! 2017.11.01 13:57 신고  댓글주소  수정/삭제  댓글쓰기

    소스 코드 도움 많이 되었어요! 감사합니다 ㅎㅎ