[c++] 알고리즘 - 합병 정렬

합병 정렬 (Merge Sort)

- 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함

- 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임

- 두 부분배열의 크기가 동일하도록 분할함

 

 

 

 

성능 특성

- 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨

- 순차적 방식에 의해 데이터를 접근함

- 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능

- N 에 비례하는 추가 기억장소가 필요함

 

- 안정적이지만 제자리 정렬은 아님

- 최악의 경우 시간 복잡도 O(N logN)

- 입력 배열에 민감하지 않음

 

 

 

 

 

수행 과정 

 

 

 

 

 

 

퀵 정렬과 비교

퀵 정렬 : 정복-분할(conquer-and-divide)

- 순환 호출이 이루어지기 전에 대부분의 작업이 수행

- 가장 큰 부분화일로부터 시작하여 가장 작은 부분화일에서 종료됨 ® 스택이 필요함

- 불안정적

합병 정렬 : 분할-정복(divide-and-conquer)

- 처음에 화일을 두 부분으로 분할하고 나서, 각각의 부분을 개별적으로 정복함

- 가장 작은 부분화일로부터 시작하여 가장 큰 부분화일에서 종료됨 ® 스택이 필요 없음

- 안정적

 

 

 

 

 

소스 코드

#include <iostream>
#include <time.h>
#include <stdlib.h>

using namespace std;
const int N = 10000000;
int a[N+1];
int b[N+1];
const int TRUE = 1;
const int FALSE = 0;

inline void swap(int a[], int i, int j)
{
  int t = a[i]; a[i] = a[j]; a[j] = t;
}

void CheckTime(int a[], int n)
{
  int i, Sorted;
  Sorted = TRUE;
  for (i = 1; i < n; i++) {
    if (a[i] > a[i+1]) Sorted = FALSE;
    if (!Sorted) break;
  }
  if (Sorted) cout << "정렬 완료." << endl;
  else cout << "정렬 오류 발생." << endl;
}

void MergeSort(int a[], int l, int r)
{
  int i, j, k, m;
  if (r > l) {
    m = (r+l)/2;
    MergeSort(a, l, m);
    MergeSort(a, m+1, r);
    for (i = m+1; i > l; i--) b[i-1] = a[i-1];
    for (j = m; j < r; j++) b[r+m-j] = a[j+1];
    for (k = l; k <= r; k++)
      a[k] = (b[i] < b[j]) ? b[i++] : b[j--];
  }
}

void main()
{
  //int i;
  //double start_time;

  //srand(time(NULL));
  //for (i = 1; i <= N; i++) a[i] = rand();

  //start_time = clock();
  MergeSort(a, 1, N);
  //cout << "합병 정렬의 실행 시간 (N = " << N << ") : " <<
           clock() - start_time << endl;
  //CheckTime(a, N);
}