[ Algorithm ] Merge Sort, Heap Sort?

Merge sort 이란?

         분할 정복(divide and Conquer)에 속하는 알고리즘 중 하나로, "폰 노이만(von Neumann)"이라는 사람이 제안하였다.

         하나의 배열을 분할하고, 분할된 배열을 정렬하고, 분할된 배열을 합하여, 최종적으로 정렬하는 알고리즘이다.

 

         시간복잡도(Time Complexity)         

                 - O(nlogN)

Merge sort 동작

         1. 배열을 중간 index를 기준으로 좌, 우로 나눕니다. (부분 배열이 1개가 남을 때까지 계속해서 반복.)

         2. 이후, 합병을 진행하는데 배열 내 요소의 대소 비교를 한 후, 배열을 합병합니다.

Merge sort with C/C++

void merge(element initList[]. int i, int m, int n) {
     int j, k, t;
     j = m + 1;
     k = i;
     
     while (i <= m && j <= n) {						// input Max num
          if (initList[i].key <= initList[i].key)
               mergeList[k++] = initList[i++];
          else
               mergeList[k++] = initList[j++];
     }
     
     if (i > m)
          for (t = j; t <= n; t++)
               mergeList[k++] = initList[t];
     else
          for (t = i; t <= m; t++)
               mergeList[k++] = initList[t];
     for (t = i; t <= n; t++)
          initList[t] = mergeList[t];
}

void mergeSort(element a[], int left, int right) {
     if (left >= right)
         return right;
     int mid = (left + right) / 2;
     mergeSort(a, left);
     mergeSort(a, right);
     mergeSort(a, left, mid, right);
}

Heap sort 이란?

         최대 힙 트리 혹은 최소 힙 트리를 구성하여, 정렬을 하는 방식이다.

         완전 이진 트리(Binary Search Tree)에서 파생된 heap 특성을 활용하여 정렬하는 알고리즘으로,

         힙은 부모의 값이 자식의 값보다 항상 크거나 작다라는 조건을 만족하는 완전이진트리 형태의 자료구조이다.
         

 

         시간복잡도(Time Complexity)         

                 - O(nlogN)

Heap sort 동작

         1. 힙 정렬을 위해 우선 힙을 생성합니다.

         2. 힙의 루트 노드의 값을 정렬 배열에 추가하고, 루트 노드의 값을 제거합니다.

         3. 이후 다시 힙으로 만듭니다. ( 1 ~ 2의 과정을 반복합니다.)

Heap sort with C/C++

void heapsort(element list[], int n) {
    int i, j;
    element temp;
    
    for (i = n/2; i > 0; i--)
        adjust(list, i, n);
    for (i = n - 1; i > 0; i--) {
        SWAP(list[1], list[i+1], temp);
        adjust(list, 1, i);
    }

}

void adjust(element list[], int root, int n) {
    int child, rootkey;
    element temp;
    temp = list[root];
    rootkey = list[root].key;
    
    child = 2 * root;
    while (child <= n) {
        if (child < n && list[child].key < list[child+1].key)
            child++;
        if (rootkey > list[child].key )
            break;
        else {
            list[child/2] = list[child];
            child *= 2;
        }
    }
    list[child/2] = temp;
}