Selection Sort 증명

이번 포스팅에서는 선택정렬(Selection Sort) 알고리즘을 증명해보자.

selection sort 는 알고리즘을 처음 접하면 알게 되는 녀석이다. 

하지만 이 역시 수학적으로 엄밀하게 증명해본 적이 없어 이를 증명해보고자 한다.

 

 

selection sort 소스코드

// Selection Sort
int sort(int a[], int n){
    int i, j, m, t;
    for(i=0;i<n;i++){
        // Find Minimum
        m = i;
        for(j=i; j<n; j++)
            if(a[m] > a[j])
                m=j;

        t = a[i];
        a[i] = a[m];
        a[m] = t;
        // a[m] : 최소값, a[i] ~ a[n-1] 중에
    }
    return -1;
}

 

Sorting 알고리즘의 정확성 증명

 

우선 정렬이 완료됐다는 걸 어떻게 증명할 것인가? 에 대한 답을 내려야 한다.

• 입력값 : a[0], a[1], .... ,a[n-1] 
• 입력값은 정수 집합이다.

정렬이 완료되었다는 것, 즉 Sorting이 완료된 후에는 다음을 만족해야 한다.

 

• Sorting 이 끝난 후의 배열을 편의상  b[0], b[1], ..... b[n-1] 이라 하자.
• 같은 배열이지만 구분을 위해 이름만 다르게 한 것이다. (b는 배열 a와 같음.

조건 1: 집합조건이 성립

• { a[0], a[1], ..... ,a[n-1] } = { b[0], b[1], .... , b[n-1] } 집합으로 같음

조건 2: b[0] < b[1] < ...... < b[n-1]

b[k] = b[k+1]인 경우는 부등호가 달라져야 하겠지만, 편의상 같은 값을 없다고 가정하겠다.

 

위 조건 1, 2 가 만족되면 sorting이 증명됐다고 볼 수 있다.

 

Proof by Invariant

앞서 binary search 에서도 invariant로 증명을 하였는데, 선택정렬도 invariant 를 통해 증명해보자.

(Invariant 란 불변 조건으로, 함수가 실행되는 동안 이 조건이 깨지지 않으면 증명된다.)

 

Invariant

(1) 집합조건이 깨지지 않는다.

(2) k번째 루프가 끝난 후에는 다음이 성립한다.

•  a[0] < a[1] < ..... < a[k-1]
•  x > k-1 이라면 a[k-1] < a[x] 가 성립한다.

Proof Invariant 

수학적 귀납법을 이용해 불변조건을 증명해보자.

 

Base 

k=0일 때 (1)은 null condition,  true. (2)도 null이므로, true.

성립할 조건이 아예 없으면 true이다. 따라서 Invariant 는 성립한다.

 

Step

P(k) : k+1 번째 루프를 돌고 난 후에 Invariant 가 성립.

P(k-1) -> P(k) 임을 보여야 한다.

 

Invariant

P(k-1) 이 사실이라고 가정했으므로 (루프 k번 돌음)

(1) a[0] < a[1] < ...... < a[k-1] 을 만족한다.

(2) x > k-1 일때 a[k-1] < a[x] 을 만족한다.

 

P(k)

K+1 번째 루트가 끝난 다음에 가장 작은 값을 k 에 가져다 뒀으므로

Invariant (2) :  x > k 일 때 a[k] < a[x] 가 성립한다.

 

이제 Invariant (1) : a[0] < a[1] < ..... < a[k] 임을 보이면 되는데,

앞의 P(k-1)이 참이므로 a[k-1] < a[k] 만 보이면 끝이다.

a[k]는 P(k-1)의 Invariant (2) 에 의해 a[k-1] 보다 크므로, a[k-1] < a[k] 임이 증명되었다. 따라서 k일때도 Invariant 가 성립한다.

 

따라서 P(k-1) -> P(k) 가 성립한다.

즉 k 번째 루프가 끝났을 때 Invariant 가 성립한다면, k+1 번째 루트가 끝났을 때도 Invariant 가 성립한다.

 

결론

수학적 귀납법에 의해 Invariant 가 항상 성립함을 보였다. 따라서 Sorting 은 참이다.

 

 

COMPLEXITY

T(N) = N + T(N-1) = N + N-1 + T(N-2) = ....... = O(N^2)

 

 

다음은 재귀적으로 선택정렬을 구현한 코드이다.

// resursive Selection sort
int sort(int a[], int n){
    int j,m,t;
    if(n<=1) return;
    m=0;
    
    for(j=0;j<n;j++){
        if(a[m]>a[j]) m=j;
    }
    // a[0]와 a[m] swap
    t = a[0]; a[0] = a[m]; a[m]=t;
    sort(a+1, n-1);
    return -1;
}

 

앞서 일반 selection sort 의 증명 방법과 비슷하다. 이번에는 수학적 귀납법만으로 증명 가능하다.

 

sorting 되었다는 증명 조건

입력:  a[0], a[1], ..... ,a[n-1] 정수 집합.

 

sorting 이 끝난 후 다음을 만족해야 한다.

• 조건 1 : {a[0], a[1], .... ,a[n-1] } = {b[0], b[1], ..... ,b[n-1] } 집합으로 같음
• 조건 2 : b[0] < b[1] < ..... < b[n-1]  (증명 편의상 같은 값은 없다고 가정)

 

Proof By Induction 

집합 조건을 깰 수 있는 코드는 지금도 없다. 따라서 집합 조건을 만족.

Base : n = 1. 정렬 할 것도 없다. true

Step :

n-1 일 때 sort() 함수가 성공한다면, n 일 때 sort() 함수가 성공한다. 를 보이자.

Sort 함수 내부에 Sort(a+1, n-1) 가 재귀적으로 호출되므로 이를 이용.

P(n-1) : sort(a+1, n-1)

P(n) : sort(a, n) 이라 하자.

 

P(n-1) 이 참이라 가정할 때, P(n) 도 참임을 보이자.

즉 재귀호출이 끝난 후 a[1] < a[2] < ..... < a[n-1] 라면 함수가 끝날 때 a[0] < a[1] < ...... <a[n-1] 임을 보이자.

 

위의 소스코드를 유심히 보자.

재귀호출을 하기 전, for문을 돈 후에 swap을 통해 가장 작은 값을 앞으로 옮기지 않았는가.

즉 a[0]이 가장 작은 값이라는 것. a[0] < a[1], a[2], ..... ,a[n-1] 임은 자명하다.

따라서 a[1] < a[2] < ..... < a[n-1] 이라면  a[0] < a[1] < a[2] ..... < a[n-1] 은 참이다.

 

Conclusion

Base, Step 에 의해 귀납적으로 sort 는 참이다.

 

COMPLEXITY

T(N) =

N + T(N-1) =

N + (N-1) + T(N-2) = ........ 

= O(N^2) 이다.