한빛출판네트워크

저자: 김대곤

필자가 본 대부분의 알고리즘 관련 서적에 등장하는 병합 정렬 알고리즘은 정렬 파트나 알고리즘 기본 디자인 원리 중에 하나인 분할 점령(Divide and Conquer) 파트에 예제로 등장합니다. 오늘은 Induction과 관련해서 이 대표적인 정렬 알고리즘이 어떻게 작동하는지 살펴보도록 하겠습니다. 이러한 접근은 실제로 알고리즘을 디자인할 때 유용하리라 생각됩니다.

먼저, 아래에 주어진 두 개의 배열이 있다고 가정해 봅시다.





규칙은 간단합니다. 문자는 숫자보다 큽니다. 문자는 알파벳 순으로 크기를 지정합니다. 즉 B는 A보다 큽니다. 즉 우리의 목표는 다음과 같이 하나의 정렬된 배열을 구하는 것입니다.





얼마 정도의 시간이 필요할까요? 이 질문에 대답하기 이전에 다른 두 개의 배열을 보여드리겠습니다. 만약 선택의 자유가 있다면 위에 주어진 두 개의 배열과 아래에 있는 두 개의 배열 중에서 어느 것을 사용하시겠습니까?





위에 있는 두 개의 배열은 전체적으로는 아니지만 부분적으로 이미 정렬되어 있습니다. 첫 눈에 정렬된 배열을 받는 것이 유리해 보입니다. 얼마 정도에 시간을 걸릴까요? 12개의 빈 자리에 정렬된 순서로 각 원소를 놓는데 다른 원소와 몇 번 비교가 되어야 할까요? 각 원소마다 한 번의 비교로 충분합니다. 먼저 각 배열에서 첫번째 원소들(1과 2)를 가져옵니다. 적은 원소(1)를 12개의 첫 칸에 놓습니다. 이제 내려간 원소가 있던 배열에서 다음 원소(4)를 가져옵니다. 4가 2보다 크기 때문에 이번에는 2를 두번째 칸에 내려 놓고, 2가 있었던 배열에서 2 다음에 있는 원소(3)를 가져옵니다. 이것을 모든 원소에 대하여 반복하면, 하나의 정렬된 배열을 얻게 됩니다. 위의 과정은 아래의 그림에 나타나 있습니다. 만약 정렬되지 않은 두 개의 배열로 다음과 같은 과정을 하면 어떻게 될까요? 바르게 정렬되지 않을 것입니다. 즉 적어도 하나의 비교를 통해서 원소 하나의 위치를 결정할 수 없게 됩니다.





정렬 문제는 다음과 같이 정의 됩니다. 입력은 하나의 리스트 입니다. 결과값은 또 다른 리스트 입니다. 이 리스트는 두 가지 속성을 가지고 있습니다. 하나는 b(i)<=b(i+1) (i=1,2,…,n-1) 이고 의 순열입니다. 즉 에서 단순히 순서만 바뀐 리스트입니다.

정렬 문제의 정의에서 알 수 있듯이 입력되는 값은 정렬된 두 개의 리스트가 아닙니다. 여기에 Induction의 묘미가 있습니다. 위에서 보여진 과정은 Induction의 두 가지 구성요소 중 Inductive step입니다. 우리에게 필요한 것은 오직 Base case입니다. 베이스 케이스는 입력되는 리스트가 하나의 원소로 구성된 경우입니다. 입력값이 그대로 결과값입니다. 이 경우에는 아래 코드에서 볼 수 있듯이 호출될 필요가 없습니다.


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class MergeSort {
         
         public static void main(String[] args) {
                  
                  int size = 0;
                  int[] A = null;
                  // Make pipe from stardard input..
                  BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
                  
                  try {
                           // Ask size of a list.
                           System.out.print("Enter the size of integer list to be sorted: ");
                           size = Integer.parseInt(stdin.readLine());
                           
                           if ( size < 1 ) {
                                    System.out.println("Size should be postive integer");
                                    System.exit(0);
                           }
                           
                           A = new int[size];
                           
                           for ( int i=0; i < size ; i++ ) {
                                    System.out.println("Enter an integer(" + (i+1) + "): ");
                                    A[i] = Integer.parseInt(stdin.readLine());
                           }
                           
                           System.out.print("Original list : <");
                           for ( int i=0; i < size-1 ; i++ ) {
                                    System.out.print(A[i] + ", ");
                           }
                           System.out.println(A[size-1] + ">");
                           
                           mergeSort(A, 0, size-1);

                           System.out.print("Sorted list : <");
                           for ( int i=0; i < size-1 ; i++ ) {
                                    System.out.print(A[i] + ", ");
                           }
                           System.out.println(A[size-1] + ">");
                           
                           
                           
                  } catch(NumberFormatException nfe) {
                           System.out.println("Input should be numbers");
                  } catch(IOException ioe) {
                           System.out.println("IOException happens");
                  } finally {
                  }

                  
                  
         }
         
         public static void mergeSort(int[] A, int p, int r) {
                  if ( p < r ) {
                           mergeSort(A, p, (int)((p+r)/2));
                           mergeSort(A, (int)((p+r)/2)+1, r);
                           merge(A, p, (int)((p+r)/2), r);
                  }
         }
         
         public static int[] merge(int[] A, int p, int q, int r) {
                  
                  int j=p, k=q+1;
                  int[] result = new int[r-p+1];
         
                  for ( int i=0; i < r-p+1; i++ ) {
                   if ( j <= q && k <= r ) {
                                    if ( A[j] <= A[k] ) {
                                             result[i] = A[j];
                                             j++;
                                    } else {
                                             result[i] = A[k];
                                             k++;
                                    }
                           /* All elements of A is removed */
                           } else if ( j > q ) {
                                    result[i] = A[k];
                                    k++;
                           /* All elements of B is removed */
                           } else if ( k > r ) {
                                    result[i] = A[j];
                                    j++;
                           }
                  }
                  
                  for ( int i=0; i < result.length ; i++ ) {
                           A[p+i] = result[i];
                  }
                  
                  return A;
         }

}


위에 구현된 병합처리는 일반적인 구현과는 조금 다릅니다. 다르게 구현한 이유는 소요시간이 좀 더 명확하게 드러나도록 하기 위해서입니다. 동일한 실행횟수를 가지는 두 개의 반복문이 있습니다. 이 구현이 좀 더 병합처리 과정을 쉽게 보여주기 때문입니다. 전체 소요시간 T(n)은 다음과 같이 표현될 수 있습니다.

T(n) = 2 T(n/2) + 2n. ( n 은 입력 리스트의 크기입니다)

이것을 쉽게 바꾸면 T(n) = O(n * log(n)) 입니다. 여기서 사용된 빅 오메가(O)는 다음 기사에서 그 의미를 상세하게 다루도록 하겠습니다.

앞의 과정을 유심히 살펴보면, 알고리즘 디자인시에 유용한 하나의 원리를 발견하게 됩니다. 즉 가정하는 것입니다. 고등학교 다닐 때 가끔 친구들과 치기 어린 말다툼을 할 때가 자주 있었습니다. 이런 식이죠. “네가 여자친구가 사귈 수 있으면 난 열 명도 사귈 수 없어”. “임마 네가 열 명 사귀면, 난 백 명 사귈 수 없어.” 사실은 한 명도 없었지만 말이죠. 알고리즘도 그와 같습니다. 네가 이것을 해 주면, 난 그걸 가지고 이런 것도 만들 수 있어. 특히 복잡한 것을 해 달라고 하고 쉬운 것을 본인이 하는 것입니다.