합병정렬(MergeSort)_(1)

1. 합병정렬
- 문제: n개 키를 비내림차순으로 정렬
- 입력: 양의 정수 n, 키의 배열 S(첨자는 1부터 n까지)
- 출력: 키가 비내림차순으로 정렬된 배열 S

2. 합병
- 문제: 2개의 정렬된 배열을 하나의 정렬된 배열로 합병
- 입력: 양의 정수 h와 m, 정렬된 키의 배열 U(첨자는 1부터 h까지), 정렬된 키의 배열 V(첨자는 1부터 m까지)
- 출력: U와 Ω의 키들을 모두 포함하여 정렬한 배열 S(첨자는 1부터 h+m까지)

3. 소스
void merge(int h, int m, int* U, int* V, int* s);
void mergesort(int n, int* s, int step);

int main(int argc, char* argv[])
{
 int s[] = {27, 10, 12, 20, 25, 13, 15, 22};
 int count=0;
 int step=0;

 count = sizeof(s)/sizeof(int)-1;
 mergesort(count, s, step);
 
 for( int i=0 ; i<count-1 ; i++ )
  cout << s[i] << endl;

 return 0;
}

void merge(int h, int m, int* U, int* V, int* s)
{
 int i, j, k;

 i=0; j=0; k=0;
 while( i<=h && j<=m )
 {
  if( U[i] < V[j] )
  {
   s[k] = U[i];
   i++;
  }
  else
  {
   s[k] = V[j];
   j++;
  }
  k++;
 }

 if( i>h )
 {
  for( int tmp=0 ; tmp<(m-j) ; tmp++ )
   s[k+tmp] = V[tmp+j];
 }
 else
 {
  for( int tmp=0 ; tmp<(h-i) ; tmp++)
   s[k+tmp] = U[i+tmp];
 }
}

void mergesort(int n, int* s, int step)
{
 const int h = n/2;
 const int m = n-h;

 /*h = (int)(n / 2);
 m = (int)(n - h);*/

 int U[h];    // 왜 이거 에러뜰까? 동적으로 할당도 해봤는데 gcc로는 되는데 비주얼에서는 안된다. -_-+
 int V[m];    // error C2057: 상수 식이 필요합니다. / error C2466: 상수 크기 0의 배열을 할당할 수 없습니다.
       // error C2133: 'U' : 알 수 없는 크기입니다.

 int step1 = 0;

 cout << "Step : " << step << endl;

 if( n>1 )
 {
  for( int i=0 ; i<h ; i++ )
  {
   U[i] = s[i];
  }
  for( int i=h+1, j=0 ; i<n ; i++, j++ )
  {
   V[j] = s[i];
  }
  step1 = step + 1;
  mergesort(h, U, step1);
  step1 = step + 1;
  mergesort(m, V, step1);
  merge(h, m, U, V, s);
 }
}