[Algorithm] 병합정렬(분할정복)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

결합 기법을 사용한 배열 합치기 문제의 확장판? 이라고 생각하면 된다.

ㅇ 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 정렬하는 알고리즘

부분집합으로 분할(divide), 각 부분집합에 대해서 정렬 작업을 완성(conquer) 한 후, 정렬된 부분집합들을 다시 결합(conbime)하는 분할 정복(divide and conquer) 기법 사용

ㅇ n-way 병합 : n 개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법

  - 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할

  - 정복(conquer) : 부분집합의 원소들을 정렬. 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용

  - 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 결합

  - 1, 2, 3의 과정을 반복 수행하면서 정렬을 완성

ㅇ 복잡하지만 효율적

ㅇ time complexity

  - Best : O(nlog2n)

  - Average : O(nlog2n)

  - Worst : O(nlog2n)

#. Code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int a[101], tmp[101];
 
void divide(int lt, int rt){
    int mid;
    int p1, p2, p3;
  
        divide(lt, mid);
        divide(mid+1, rt);
 
        p1=lt;
        p2=mid+1;
        p3=lt;
 
        while(p1<=mid && p2<=rt){
            if(a[p1]<a[p2]) tmp[p3++]=a[p1++];
            else tmp[p3++]=a[p2++];
        }
        while(p1<=mid) tmp[p3++]=a[p1++];
        while(p2<=rt) tmp[p3++]=a[p2++];
 
        for(int i=lt; i<=rt; i++)
            a[i]=tmp[i];
    }
}
 
int main() {
    int n, i;
 
    scanf("%d", &n);
 
    for(i=1; i<=n; i++)
        scanf("%d", &a[i]);
    
    divide(1, n);
 
    for(i=1; i<=n; i++)
        printf("%d ", a[i]);
    
    return 0;
}

#. Comment

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int a[101], tmp[101];
 
void divide(int lt, int rt) {
    int mid;
    int p1, p2, p3;
 
    // 후위 순회
    if (lt < rt) {
        mid = (lt + rt) / 2;
 
        /////////////////////////////
        // 분할 정복 (Divide & Conquer)
        /////////////////////////////
 
        // 왼쪽 자식 노드 호출
        divide(lt, mid);
 
        // 오르쪽 자식 노드 호출
        divide(mid + 1, rt);
 
        /////////////////////////////
        // 병합 (Combine)
        /////////////////////////////
 
        // 자식 노드 호출을 마친 뒤에야 부모 노드의 정렬 작업
        p1 = lt;
        p2 = mid + 1;
        p3 = lt;
 
        while (p1 <= mid && p2 <= rt) {
            if (a[p1] < a[p2]) tmp[p3++] = a[p1++];
            else tmp[p3++] = a[p2++];
        }
 
        // 정렬하지 않아도 되었던 나머지 원소들을 담기
        while (p1 <= mid) tmp[p3++] = a[p1++];
        while (p2 <= rt) tmp[p3++] = a[p2++];
 
        // tmp 에 저장된 정렬된 원소들을 원본에 복사
        for (int i = lt; i <= rt; i++)
            a[i] = tmp[i];
    }
}
 
int main() {
    int n, i;
 
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    divide(1, n);
 
    for (i = 1; i <= n; i++)
        printf("%d ", a[i]);
 
    return 0;
}

위 코드의 과정을 간략하게 그림으로 그려보았다.

D(1,2) 는 D(1), D(2) 로 나뉘게 되면 if(lt < rt) 조건으로 함수가 바로 종료되어버리므로

따로 함께 그리지는 않았다.

if(lt < rt) 조건을 만족하게되면

line 15 처럼 mid 값을 구해준다. (mid 값을 구해주는 이유는 분할을 하기 위해서!)

line 22, line 25 와 같이

분할은 Left 부터 mid, mid+1 부터 Right 로 이루어진다.

D(lt, mid), D(mid+1, rt)

더이상 나누어지지 않을 때까지(ex. D(1), D(2)) 나눈다.

다 나누었다면 부모 노드들의 작업이

line 32 부터 시작된다.

line 32~34, 먼저 포인터 변수 p1, p2, p3 의 위치를 세팅한다.

p1, p2 는 원본 배열에서의 포인터고, p3 는 temp 배열에서의 포인터라고 생각하면 된다.

p1 은 lt, p2 는 mid+1 로 설정한 이유는 분할된 각 배열의 첫 번째 원소의 위치를 저장한 것이다.

그리고 p3 는 분할된 두 배열을 합쳤을 때 저장될 첫 번째 원소의 위치이다.

line 36~39, 분할된 두 배열의 첫 번째 원소부터 각 배열의 끝 원소의 위치까지 반복하게 된다.

여기서 작은 원소를 먼저 temp 배열에 저장한다.

line 42~43, 위 동작에서 p1 <= mid && p2 <= rt 를 만족하지 않고 더이상 정렬할 필요가 없어져 반복문이 종료되었을 때,

나머지 원소들을 temp 에 저장해주어야 하므로 이 작업이 필요하다.

line 46~47

원본 배열의 원소들을 정렬한 결과를 temp 배열에 저장해두었었다.

여기서 병합하면서 정렬된 원소들을 다시 원본 배열에 복사한다.

--

재귀함수가 생각보다 복잡했지만 막상 알고보면

딱 조건대로 적어주기만하면 알아서 완전 탐색을 수행하므로

약간의 틀만 익힌다면 쉽게 처리해낼 수 있을 것 같다.

빨리 익숙해지자 재귀야..!

#. Result

  - Input --------------------------------------------------------

8

7 6 3 1 5 2 4 8

------------------------------------------------------------------

  - Output --------------------------------------------------------

1 2 3 4 5 6 7 8

------------------------------------------------------------------