C - merge sort

전형적인 divide-and-conquer 알고리즘이다.

divide-and-conquer이란, 큰 문제를 작은 문제로 쪼개고 쪼개서, 작은 문제를 푼 후 결과를 병합하여 푸는 방법을 의미한다.

#include <stdio.h>
#define max 6

//conquer
void merge(int a[], int low, int mid, int high){
  int b[1000]; // sort된 배열을 넣을 새로운 배열
  int i=low, j=mid+1; //i는 왼쪽 배열의 시작, j는 오른쪽 배열의 시작
  int k=0; //k는 새로 sorted된 array의 현재 위치
  
  //한쪽이 다른 한쪽보다 완전히 작을때까지
  while(i<=mid && j<=high) {
    if(a[i] < a[j]){
      b[k] = a[i];
      k++;
      i++; 
    } else {
      b[k] = a[j];
      k++;
      j++;
    }
  }
  //만약에 왼쪽 배열이 남아있으면, 나머지 왼쪽 배열을 그대로 b array에 넣어줌
  while(i <= mid) {
    b[k]=a[i];
    k++;
    i++;
  }
  //만약에 오른쪽 배열이 남아있으면, 나머지 오른쪽 배열을 그대로 b array에!
  while(j <= high) {
    b[k]=a[j];
    j++;
    k++;
  }
  //마지막에 한번 더 k가 플러스 됐기 때문에 -1
  k--;
  // 새로 만들었던 b배열의 정보를 기존 a배열에 그대로 넣어준다.
  while(k>=0) {
    a[low+k] = b[k];
    k--;
  }
}
//divide
void mergeSort(int a[], int low, int high) {
  // low<high이면 a array의 원소가 하나일 때를 의미
  if(low < high) {
    int mid = (low+high) / 2;
    // 나눠진 배열의 왼쪽 부분
    mergeSort(a, low, mid);
    // 오른쪽 부분
    mergeSort(a, mid+1, high);
    merge(a, low, mid, high);
  }else {
    return;
  }
}

int main() 
{
  int A[max] = { 5, 12, 6, 80, 2, 15 };

  printf("unsorted: ");
  for(int i=0 ; i<max ; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");

  mergeSort(A, 0, max-1);

  printf("sorted: ");
  for(int i=0 ; i<max ; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");

  return 0;
}