[자료구조] 합병정렬(Merge Sort)의 증명

합병정렬

int sort(int a[], int n) {
    int h;
    int b[n];
    h = n / 2;
    // copy a[] to b[]
    sort(b, h);
    sort(b+h, n-h);
    // Merge two halves in b to a
    return 0;
}

• 정렬된 두 가지 배열을 정렬되도록 합치는 것이 Merge(합병)이다.
• 배열을 가장 작게 쪼갠 뒤, 이들을 계속해서 Merge하면 최종적인 배열이 정렬될 것이다.
• 반복문으로도 구현할 수 있지만, 조금 복잡해져서 재귀를 활용했다.
• copy와 merge 코드 구현부는 제외하고 서술했다.
• 시간복잡도 O(N*logN)

합병정렬의 증명

입력 집합 a[0],a[1],...,a[n-1] 의 정수 집합에 대해 Sorting이 완료된 집합은 b[0],b[1],...,b[n-1] 이라고 하자. (두 집합은 같은 배열이지만 구분을 위해 이름만 다르게 부른 것임.)

 

1. Sorting이 완료되려면 다음 두가지가 만족되어야 한다.

• 조건 1 : 두 집합은 같아야 한다.
• 조건 2 : b[0] < b[1] < ... < b[n-1] 이어야 한다. (편의상 같은 값은 없다고 가정한다.)

2. 조건 1 (집합조건) 을 깰 수 있는 코드는 없다.

 

3. Proof by Invariant (루프가 돌아가는 동안 변화하지 않는 성질인 roof invariant를 잘 찾아 증명하자.)

• invariant(1) : k번째 루프가 끝난 후에, a[0] < a[1] < ... < a[k-1]가 성립된다.
• invariant(2) : k번째 루프가 끝난 후에, x > k - 1 라면 a[x] > a[k-1] 가 성립한다.

4. Prove Invariant by induction

• Base : 'n = 1 일 때 invariant가 성립한다.'
• -> 아무것도 수행하지 않는다. (null condition으로 true)
• Step : 'n-1일 때 sort 함수가 성공하면 (재귀 호출 종료 후 a[0] < a[1] < ... < a[n/2 - 1] & a[n / 2] < a[n/2 + 1] < ... < a[n-1] 이라면), n일 때 sort 함수가 성공한다. (함수가 끝날 때 a[0] < a[1] < a[2] < a[n-1] 성립)' 
• -> merge 기능이 정확하다는 가정하에, 성립한다.
• merge에 대한 증명도 필요하지만 현재 학습과정에서는 중요한 것이 아니므로 Skip했다. Merge라는 기능은 정확하다고 가정한다.

- 증명완료