[C] Merge Sort 알고리즘 (합병 정렬)

#include <stdio.h>

void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);
void printArray(int arr[], int length);

int ms = 1; //mergeSort 함수 호출 횟수, 필수 아님
int m = 1; //merge 함수 호출 횟수, 필수 아님
int temp[6]; //임시 배열 생성

int main(void) {
  int arr[6] = {29, 30, 6, 26, 23, 2};

  printf("\nBefore Sorting : ");
  printArray(arr, 6);

  mergeSort(arr, 0, 5);

  printf("\nAfter Sorting : ");
  printArray(arr, 6);
}

void printArray(int arr[], int length) {
  for (int i = 0; i < length; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;

    //눈으로 확인하기 위한 코드
    printf("%dth mergeSort : left = %d, mid = %d, right = %d \n", ms, left, mid,
           right);
    ms++;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
  }
}

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

  //눈으로 확인하기 위한 코드
  printf("%dth merge : left = %d, mid = %d, right = %d \n", m, left, mid,
         right);
  m++;

  int L = left;    //왼쪽 배열의 시작 인덱스, 끝은 mid
  int R = mid + 1; //오른쪽 배열의 시작 인덱스, 끝은 right
  int n = left;    // temp 배열의 인덱스

  while (L <= mid && R <= right) {
    if (arr[L] <= arr[R]) {
      temp[n++] = arr[L++];
    } else {
      temp[n++] = arr[R++];
    }
  }

  //남아있는 것들 정리
  if (L > mid) { //왼쪽 배열은 다 끝났는데 오른쪽 배열이 남아있다면
    for (int i = R; i <= right; i++) {
      temp[n++] = arr[i];
    }
  } else {
    for (int i = L; i <= mid; i++) {
      temp[n++] = arr[i];
    }
  }
  //원래 배열에 정렬된 temp 배열을 넣기

  for (int i = left; i <= right; i++) {
    arr[i] = temp[i];
  }
}

Before Sorting : 29 30 6 26 23 2 
1th mergeSort : left = 0, mid = 2, right = 5
2th mergeSort : left = 0, mid = 1, right = 2
3th mergeSort : left = 0, mid = 0, right = 1
1th merge : left = 0, mid = 0, right = 1
2th merge : left = 0, mid = 1, right = 2
4th mergeSort : left = 3, mid = 4, right = 5
5th mergeSort : left = 3, mid = 3, right = 4
3th merge : left = 3, mid = 3, right = 4
4th merge : left = 3, mid = 4, right = 5
5th merge : left = 0, mid = 2, right = 5

After Sorting : 2 6 23 26 29 30

코드 설계

분할 정복 알고리즘인 머지 소트는 개별 요소로 분할 후 정복하는 과정에서 정렬이 이루어진다.

1. 하나가 될 때까지 모두 분할한다.
2. 왼쪽 배열과 오른쪽 배열을 합친다.
   1. 이 때, 새로운 임시 배열에 값을 정렬시키고
   2. 정렬이 끝났다면 원래 배열에 그 값을 복사한다.

코드 설명 (미완)

• mergeSort(int arr[], int left, int right);

void mergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;

    //눈으로 확인하기 위한 코드
    printf("%dth mergeSort : left = %d, mid = %d, right = %d \n", ms, left, mid,
           right);
    ms++;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
  }
}

 

인수로 머지 소트의 대상인 원본 배열과, 가장 왼쪽 인덱스, 가장 오른쪽 인덱스를 넘겨줌으로써 해당 머지소트의 대상인 작은 배열을 넘겨준다.

 

넘겨받은 배열의 요소가 1개보다 많다면, left보다 right가 클 것이다. 1개가 될 때까지 분할해야하므로 해당 조건을 재귀적 호출 조건으로 사용한다.