[알고리즘] 분할 정복 기법 (Divide - and - Conquer) - 3. 합병정렬(Mergesort)

. N개의 숫자들을 정렬하는 방법
 ⓐ 알고리즘(명백한 방법)
  - 최대값을 찾는다.
  - 남아 있는 숫자들을 회귀적으로 정렬한다.

 ⓑ 분석
  - 요구되는 비교 횟수
    (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = ⊝(n^2)
     > 명백히 이 방법은 "균형취하기"발견법(Heuristic)을 이용하지 않는다.


 ⓓ 새로운 알고리즘 전략 : 합병정렬
  - 배열을 반(Half)로 나눈다.
  - 두개의 부분들을 각각 정렬한다.
  - 정렬한 두 개의 부분들을 병합한다.
  ex) 27 10 12 20 25 13 15 22를 정렬하라.

       

 ⓔ 새로운 알고리즘 구현
  //배열 a[i...j]를 정렬한다.
  void Mergesort(int i, int j){
    int mid;
    if ( i > j ) {
      mid = floor(i+j)/2;
      Mergesort(i,mid);     // 분할
      Mergesort(mid+1,j);  // 분할
      Merge(i,mid,j);         // 합병
    }
  }  
  //관찰 : 크기가 m인 부분과 크기가 n인 부분을 합병하는 것은 최악의 경우에 m + n - 1번의 비교가 필요하다.
  //정렬된 부분배열 A[low...mid]와 A[mid+1...high]를 크기 순서대로 합병한다.
  void Merge(int low, int mid, int high){
    int[] B = new int[N];
    int h,i,j,k;
    h = low; i = low; j = mid + 1;  k = high;
    // i = 배열 B에 해당하는 상수
    while ( h <= mid && j <= high ){ // 부분배열 두 파트가 모두 존재할때
      if ( A[h] <= A[j] ) { B[i] = A[h] ; h = h+1 ; }
      else { B[i] = A[j]; j = j+1 ; }
      i = i + 1 ; // 하나를 정렬하면 B배열을 다음 부분으로 이동한다.
    }
    if ( h > mid ) { // 두번째 배열만 남은 경우
      for ( k = j ; k <= mid ; k++ ) {
        B[i] = A[k]; i = i + 1;
      }
    } else { // 첫번째 배열만 남은 경우
        B[i] = A[k]; i = i + 1;
    }
    for ( k  = low ; k <= high ; k++ ){  // B배열을 A배열로 복사
      A[k] = B[k];
    }
  }  

 ⓔ 새로운 알고리즘 분석 T(n) : n개의 배열 요소들을 정렬하기 위해 필요한 비교 횟수
  - T(n) = 2T(n/2) + n - 1
              └──┘ └─┘ → 최악의 경우에 합병하기 위해 필요한 횟수
                └→ 크기가 반인 두 배열을 회귀적으로 정렬하는데 필요한 횟수
     T(1) = 0
     

 ⓕ 새로운 알고리즘 관찰 : 분할 정복 프로그램에서 회귀를 제거하면 더 효율적인 프로그램이 나올 것 같다.


 ⓖ 새로운 알고리즘 : 비재귀적 합병정렬
     

  - 아이디어 : MergeSort에서 배열 부분들을 합병하는 부분을 이용한다.

 ⓗ 새로운 알고리즘의 소스
  size = 1;
  while( size < n ) {
    for ( i = 1 ; i <= n ; i = i + 2 * size ) {
      Merge(i, i+size-1, i + 2 * size - 1) ;
    }
    size = size * 2;
  }
  // Merge는 이전의 소스와 동일

 ⓘ 새로운 알고리즘 분석 
  - ⊝(logn) 단계, 각 단계는 ⊝(n)번의 비교가 필요하다. 따라서 ⊝(nlogn)
  ex)