한빛출판네트워크

저자: 한빛리포터 김대곤

Merge Sort가 취하고 있는 접근법과 Merge Sort의 실제 내용, Pseudo 코드를 살펴본 후, 이것을 자바 프로그램으로 작성하는 법을 살펴보자.

Divide-and-Conquer 접근법

실제 정렬 알고리즘에 들어가지 전에 Merge-Sort가 취하고 있는 접근법에 대해 살펴보도록 하자. Divide-and-Conquer 방법을 사용하는데, 이 접근법은 먼저 해결하고자 하는 문제를 작은 단위로 쪼갠다. 이 때는 기능을 나눌 수도 있으며, 대상을 나눌 수도 있다. 작은 단위로 나누어진 프로그램을 재귀적으로(recursive) 1회 또는 그 이상 호출하여 작은 문제를 해결한 후 단위 프로그램을 사용하여 원래 문제를 해결한다. 이 때 재귀적(recursive) 구조가 자주 사용된다.

Merge-Sort

이제 Merge-Sort에 대해 살펴보자. 정렬을 필요로 하는 정수의 배열을 다음과 같이 가정하자.

   A[1,2,3,...N]

이 때, 다음과 같은 조건을 만족하는 A의 일부분인 다음과 같은 배열에 대해 생각해보자.

   A[p,p+1,...,q,q+1,...,r] (A[p,q]와 A[q+1,r]은 이미 정렬되어진 상태인 A의 부분 배열)

이 배열을 p, r까지 정렬하는 코드가 아래에 있는 MERGE이고, 이 함수를 사용하여 자기 자신을 여러 번 호출하여 원래의 문제를 해결하는 함수가 MERGE-SORT이다. 실제 예를 통해 이러한 방법을 살펴보자. 배열 A가 다음과 같이 구성되어 있다.

[5,2,4,7,1,3,2,6]

MERGE-SORT가 호출되는 순서를 인수로 살펴보면 다음과 같다.

A, 1, 8 -> A, 1, 4 -> A, 1, 2 -> A, 1, 1 -> A, 2, 2 -> A, 3, 4 -> A, 3, 3 -> A, 4, 4
          A, 5, 8 -> A, 5, 6 -> A, 5, 5 -> A, 6, 6 -> A, 7, 8 -> A, 7, 7 -> A, 8, 8

p, r 값이 같은 경우, 하나의 값을 가진 배열은 이미 정렬된 것이기 때문에, 아무 일도 일어나지 않는다. 그러나 r값이 p값보다 큰 경우에는 MERGE가 일어난다. 이를 그림으로 나타나면 다음과 같다. 각 화살표가 MERGE를 나타낸다.

Pseudo 코드

아래에 있는 Pseudo 코드는 "Introduction to ALGORITHMS(MIT Press)"에 나온 것을 그대로 가져온 것이다. 상세한 설명은 이 책을 참조하기 바란다. 그러나 머리와 펜과 손으로 하나씩 쌓아가는 것이 훨씬 재미있고, 기억에도 남을 것이다.

먼저 MERGE에 대해 살펴보자.

MERGE(A, p, q , r)
01 n1 = q - p + 1
02 n2 = r -q
03 L[1,2,...,n1+1], R[1,2,...,n2+1] 배열 생성
04 for i <- 1 to n1
05    do L[i] <- A[p+i-1]
06 for j <- 1 to n2
07    do R[j] <- A[q+j]
08 L[n1+1] <- ∞
09 R[n2+1] <- ∞
10 i <- 1
11 j <- 1
12 for k <- p to r
13    do if L[i] <= R[j]
14       then A[k] <- L[i]
15            i <- i + 1
16       else A[k] <- R[j]
17            j <- j + 1

이제 MERGE-SORT을 살펴보자.

MERGE-SORT(A, p, r)
1 if p < r
2    then q <- (p+r)/2보다 작은 정수 중 가장 큰 수
3       MERGE-SORT(A, p, q)
4       MERGE-SORT(A, q+1, r)
5       MERGE(A, p, q, r)

이제 MERGE_SORT(A, 1, A의 크기)을 한 번 호출함으로 정렬이 된다.

자바 Code

이제 위의 내용을 자바로 구현해 보자. 일반적인 프로그램에서는 사용상의 편의 때문에 전역변수를 사용하지만, 알고리즘 책에서는 거의 전역변수를 사용하지 않는다. 몇 가지 내용을 살펴보자.

첫째, static 메소드인 main에서 실행됨으로 모든 메소드는 static으로 선언한다.

둘째, 메소드의 인자 전달시 배열과 객체는 주소값(C에서의 pointer)이 전달되며, 기본 데이터 타입(primitive data type)은 값이 전달된다. 즉, 배열과 객체는 Call-by-Reference이고, 기본 데이터 타입은 Call-by-value라는 점이다.

셋째, 무한 값은 변수가 가질 수 있는 최대 값을 선택한다. 여기서는 Integer.MAX_VAULE을 사용하였다. 이 값을 초과하는 값은 에러에 해당됨으로 실제상의 무한 값으로 취급된다.

넷째, 배열 값의 처리에서 Pseudo 코드에서는 1부터 시작하지만, 자바에서 배열의 인덱스는 0부터 시작한다. p, r 값은 배열의 인덱스를 나타냄으로 변화가 없지만, q 값은 계산된 값이 된다. 실제로 p, r이 아닌 p-1, r-1이므로, q는 [(p-1) + (r-1)]/2가 됨으로 (p+r)/2 - 1로 값이 차이가 생기게 된다. 이를 보정해 주는 부분이 필요하며, 여기서는 merge메소드에서 q++ 부분이 담당하고 있다. 이것은 다른 방법으로도 처리될 수 있다.

public class MergeSort  {

  public static void main(String[] args)  {

     int[]  arrays = new int[8];
     arrays[0] = 5;
     arrays[1] = 2;
     arrays[2] = 4;
     arrays[3] = 7;
     arrays[4] = 1;
     arrays[5] = 3;
     arrays[6] = 2;
     arrays[7] = 6;

     mergeSort(arrays, 0, arrays.length-1);

     for ( int i = 0; i < arrays.length ; i++) {
       System.out.println("Array[" + i + "] : " + arrays[i]);
     }

  }

  public static void mergeSort(int[] arr, int p, int r) {

    int q = 0;

    if ( p < r ) {
      q = (int)((p + r)/2);
      mergeSort(arr, p, q);
      mergeSort(arr, q+1, r);
      merge(arr, p, q, r);
    }
  }

  public static void merge(int[] arr, int p, int q, int r) {

    int n1 = q-p+1;
    int n2 = r-q;

    q++;

    int[] L = new int[n1+1];
    int[] R = new int[n2+1];

    int i =0;
    int j = 0;

    for ( i=0; i < L.length-1 ; i++ ) {
      L[i] = arr[p+i];
    }
    for ( j=0; j < R.length-1 ; j++ ) {
      R[j] = arr[q+j];
    }

    L[n1] = Integer.MAX_VALUE;
    R[n2] = Integer.MAX_VALUE;

    i = 0;
    j = 0;

    for ( int k = p ; k <= r ; k++ ) {
      if ( L[i] <= R[j] ) {
        arr[k] = L[i];
        i++;
      } else {
        arr[k] = R[j];
        j++;
      }
    }
  }

}

결론

전산을 전공하지 않고 대학 졸업 후 전산을 시작한 필자에게 자바를 이용하여 알고리즘이나 재귀 메소드를 작성하는 일은 한 번도 없었던 일이다. 알고리즘과 함수 또는 메소드의 재귀적 용법은 어쩌면 한가로울 수 있는 연말에 도전해 볼 만한 주제가 아닌가 한다. 사실 이 기사는 알고리즘에 대해 다루기 보다는 그것을 어떤 식으로 자바에서 코딩하는가에 대한 간단한 예를 보여주는 것에 불과하다. 그러나 알고리즘이라는 주제는 일상적으로 사용하고 있는 많은 high-level 클래스들의 기초가 이룬다는 면에서 더욱 재미있고, 사고의 폭을 넓혀 주는 주제가 아닌가 생각한다.