분할 정복(Divide and Conquer) - Merge Sort

분할 정복이란?

• 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
• 분할 정복은 대개 순환 호출을 이용하여 구현한다.

합병 정렬(merge sort) 개념

• 합병 정렬은 크게 아래 단계로 이루어진다.
  • 분할(Divide) : 입력 배열을 같은 크기의 2 배열로 분할
  • 정복(Conquer) : 부분 배열을 정렬. 부분 배열의 크기에 따라 다시 재귀 호출하여 분할 정복 실행
  • 결합(Combine) : 정렬된 부분 배열을 하나의 배열로 정렬
• 과정 
  • 추가적인 리스트가 필요함 -> 불필요한 메모리 낭비 가능성 O
  • 각 부분 배열 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용
  • 합병 정렬에서 실제 정렬이 이루어지는 시점은 2개 리스트를 합병(merge) 하는 단계

합병 정렬 Pseudo code

1. if(p < q) {                 // 배열의 원소 수가 2개 이상이면
2.     k = floor((p+q) / 2)    // k는 중간 원소의 인덱스
3.     MergeSort(A, p, k)      // 앞 부분 순환 호출
4.     MergeSort(A, k+1, q)    // 뒷 부분 순환 호출
5.     A[p]~A[k]와 A[k+1]~A[q]를 합병
6. }

 

합병 정렬 구현 코드 (.cpp)

- mergeSort()  // p : start, q : end, k : mid

void mergeSort(int A[], int start, int end) {
    if(start < end) {
        int mid = (start + end) / 2 ; // 배열 중간 인덱스를 계산
        // 1.배열을 재귀적으로 반으로 나누어 정렬
        mergeSort(A, start, mid); // 앞 부분
        mergeSort(A, mid + 1, end); //뒷 부분
        // 2.두 하위 배열을 병합
        merge(A, start, mid, end);
    }
}

중간 원소의 인덱스를 mid에 저장 후, mid를 기준으로 앞부분과 뒷부분으로 분할 후 합병(merge) 하였음

 

- merge()

void merge(int A[], int start, int mid, int end) {
    int *temp = new int[end - start + 1];   // 임시 배열 생성

    int i = start;          // 앞 부분 배열 시작 인덱스
    int j = mid + 1;        // 뒷 부분 배열 시작 인덱스
    int k = 0;              // 임시 배열 인덱스

    // 1. 앞, 뒤 배열 값 중 더 작은 값을 tmp로 복
    while (i <= mid && j <= end) {
        if (A[i] <= A[j]) {
            temp[k] = A[i];
            i++;
        }
        else {
            temp[k] = A[j];
            j++;
        }
        k++;
    }

    // 2. 앞 배열에 남은 값 있으면 temp로 복사
    if (i > mid) {
        while (j <= end) {
            temp[k] = A[j];
            k++;
            j++;
        }
    }
    // 3. 뒷 배열 남은 값 있으면 temp로 복사
    else {
        while(i <= mid) {
            temp[k] = A[i];
            k++;
            i++;
        }
    }
    // 4. temp 배열 -> 원본 배열로 복사
    for(int i=start; i<=end; i++)
        A[i] = temp[i - start];

    delete[] temp;
}

앞서 분할한 배열의 크기 만큼 temp 임시 공간 할당.

while 루프에서 두 배열의 첫 원소 값을 비교하여 더 작은 값을 temp 배열에 복사 후, 인덱스 값을 증가 시키면서 A[i], A[j] 값을 비교하며 temp에 복사 반복. 두 배열 중 하나가 먼저 끝나면, 다른 배열에 남은 원소들을 temp 배열로 복사. 이후 원본 배열로 temp 배열 값들을 복사하여 결과 도출.