[Algorithm] 합병정렬 MergeSort - C언어

분할 정복 알고리즘(Divide-and-Conquer)

• 합병정렬 MergeSort
• 퀵 정렬 QuickSort
• 선택 문제 Selection Problem

 

합병정렬(MergeSort)

: 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할

1.  n개의 숫자들을 n/2개의 부분문제로 분할(Divide)
2.  각각의 부분문제들을 해결(Conquer)
3.  재귀적으로 합병 정렬(Merge)

 

개념 설명

 

Pseudo code

MergeSort(A, p, q)
입력 : A[p] ~ A[q]
출력 : 정렬된 A[p] ~ A[q]

if(p < q){ // 배열의 원소의 수가 2개 이상이면
	k = [(p+q)/2] // k : 반으로 나누기 위한 중간 원소의 인덱스(내림으로)
	MergeSort() // 앞부분 재귀 호출
	MergeSort() // 뒷부분 재귀 호출
	A[p] ~ A[k]와 A[k+1] ~ A[q]를 합병
}

 

시간복잡도

• 시간복잡도 : O(nlogn)

-> (층수) X O(n) = log2(n) X O(n) = O(nlogn)

• 공간복잡도 : O(n)

 

단점

• 입력을 위한 메모리 공간 외에 추가로 입력과 같은 크기의 공간(임시 배열)이 별도로 필요
• 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요함

 

구현 - C언어

#include <stdio.h>
#define size 8

// 배열의 값을 분할하는 과정 + Merge
void MergeSort(int arr[], int left, int right);
// 배열의 값을 정렬후 합치는 과정
void Merge(int arr[], int left, int mid, int right);

int main(void) {
  int arrA[size] = {37, 10, 22, 30, 35, 13, 25, 24};

  // 정렬 전
  printf("before merge sort\n");
  for (int i = 0; i < size; i++) {
    printf(" [%d] %d", i, arrA[i]);
  }
  printf("\n");

  // MergeSort 수행
  MergeSort(arrA, 0, size - 1);

  // 정렬 후
  printf("after merge sort\n");
  for (int i = 0; i < size; i++) {
    printf(" [%d] %d", i, arrA[i]);
  }
  printf("\n");
  return 0;
}

void MergeSort(int arr[], int left, int right) {
  int mid;

  if (left < right) {
    mid = (left + right) / 2;  // 배열의 중간 인덱스 계산 - divide
    MergeSort(arr, left, mid); // 중간 인덱스 기준 왼쪽 배열 정렬
    MergeSort(arr, mid + 1, right); // 중간 인덱스 기준 오른쪽 배열 정렬
    Merge(arr, left, mid, right); // 정렬된 2개의 배열 합병 - merge

    // 정렬 과정
    printf("procedure : ");
    for (int i = 0; i < size; i++) {
      printf(" [%d] %d", i, arr[i]);
    }
    printf("\n");
  }
}

void Merge(int arr[], int left, int mid, int right) {
  int tmp[size];       // 정렬한 배열 저장 공간 - 추가 공간
  int l_idx = left;    // 정렬될 왼쪽 배열의 인덱스
  int r_idx = mid + 1; // 정렬될 오른쪽 배열의 인덱스
  int sort_idx = left; // 정렬된 배열의 인덱스

  // 분할된 배열의 정렬값 추가 공간에 복사
  while (l_idx <= mid && r_idx <= right) {
    // 오른쪽 배열의 값이 더 클 경우
    if (arr[l_idx] <= arr[r_idx])
      // 왼쪽 배열의 값을 추가 공간에 복사
      tmp[sort_idx++] = arr[l_idx++];

    // 왼쪽 배열의 값이 더 클 경우
    else
      // 오른쪽 배열의 값을 추가 공간에 저장
      tmp[sort_idx++] = arr[r_idx++];
  }

  // 왼쪽 배열의 값이 모두 추가 공간에 복사된 경우
  if (l_idx > mid) {
    // 오른쪽 배열의 값을 추가 공간에 일괄 복사
    for (int r = r_idx; r <= right; r++)
      tmp[sort_idx++] = arr[r];
  }

  // 오른쪽 배열의 값이 모두 추가 공간에 복사된 경우
  else {
    // 왼쪽 배열의 값을 추가 공간에 일괄 복사
    for (int l = l_idx; l <= mid; l++)
      tmp[sort_idx++] = arr[l];
  }

  // 정렬되어 추가 공간에 복사된 값을 원본 배열로 재복사
  for (int idx = left; idx <= right; idx++) {
    arr[idx] = tmp[idx];
  }
}

 

결과