[중간고사] 3-(2). Sorting - Merge Sort

Merge Sort

만약에 코드가 주어주면 시간 복잡도를 도출할 수 있는가?

MergeSort(Array, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(Array, p, q) # A[p...q]를 모두 나누기 -> 정렬
    mergeSort(Array, q+1, r)# B[q+1...r]를 모두 나누기 -> 정렬
    merge(Array, p, q, r) # 병합

 

(1) divide - and - Conquer 이론과 연결지어 설명할 수 있는가?

• Divide-and-Conquer에 기반하여 Merge하여 정렬하는 방법
• 시간 복잡도와 관련하여 각각 단계를 설명하면 다음과 같다.

1. Divide - Conquer
   배열을 두 개의 하위 배열로 나누고, 이러한 하위 배열을 정렬하는데 O(nlog n)의 시간 소요
2. Merge - 병합
   두 개의 정렬된 하위 배열을 병합하는 데 O(n) 의 시간 소요
   왜? 크기가 1인 배열이 총 n개 있으므로

 

(2) Master Theorem과 연결지어 설명할 수 있는가?

 

• 다음은 Merge Sort를 recursion tree로 표현한 그림임
• Mater Theorem에 근거하여 
  a = 2, b = 2
  g(n) = n^(logab) = n
  f(n)은 하위를 Merge하는데 소요되는 시간 n을 나타냄
                                      ∴ f(n) = n
• g(n)과 f(n)이 같은 무게이므로
  g(n)에 logn을 곱한 O(nlogn)의 시간 복잡도를 가짐

 

왜? Merge Sort는 다이나믹 프로그래밍 기법으로 하면 효율적이지 않은가?

Draw the recursion tree for the MERGE-SORT procedure an array of 16 elements.

// 16개 요소의 배열을 정렬하는 MERGE-SORT 절차의 재귀 트리
Explain why memorization fails to speed up a good divide-andconquer algorithm such as MERGE-SORT.

// 왜 메모이제이션(DP의 기법)은 MERGE-SORT와 같은 좋은 분할 정복 알고리즘의 속도를 높이는 데 실패?

DP	MERGE-SORT
Memorization	Divide-and-Conquer
중복되는 계산을 저장하고 재사용하여 알고리즘의 성능을 향상시키는 기술	이미 중복 계산을 최소화 즉, 같은 하위 문제를 반복해서 해결할 필요가 없기 때문

 

Merge Sort 코드는 이해했는가?

void merge(int arr[], int p, int q, int r) {
// Here, p = 0, q = 4, r = 6 (size of array)

    // Create L ← A[p..q] and M ← A[q+1..r]
    int n1 = q - p + 1 = 3 - 0 + 1 = 4;
    int n2 = r - q = 5 - 3 = 2;

    int L[4], M[2];

    for (int i = 0; i < 4; i++)
        L[i] = arr[p + i];
        // L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

    for (int j = 0; j < 2; j++)
        M[j] = arr[q + 1 + j];
        // M[0,1] = A[4,5] = [6,9]

    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 

    while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            arr[k] = L[i]; i++; 
        } 
        else { 
            arr[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

 

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }