[자료구조] 선택정렬(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;        
    }
    return 0;
}

• m이라는 변수를 활용해 제일 작은 값을 찾고, 위치를 교환해주는 방식으로 정렬을 진행한다.
• 시간복잡도 O(N^2)

선택정렬의 증명

입력 집합 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 : 'k = 0 일 경우 invariant가 성립한다.'
• -> invariant(1) null condition으로 true / invariant(2) null condition으로 true
• Step : 'k번째 루프가 끝났을 때 invariant가 성립한다면 k+1번째 루프가 끝났을 때도 invariant가 성립한다'
• -> k번째 루프가 끝났을 때 'a[0] < a[1] < ... < a[k-1]' 와 'x > k - 1 라면 a[x] > a[k-1]'가 성립한다고 가정하자. 그 후에 일어나는 일은 a[k],...,a[n-1] 중 최소값을 a[k]로 옮기는 것이다. 따라서 'a[0] < a[1] < ... < a[k]' 와 'x > k 라면 a[x] > a[k]'가 성립하게 된다.
• 물론 최소값을 찾는 과정의 증명도 필요하겠지만 그것까지 증명하게 되면 너무 길어지므로 이 정도만 이해하자.

-증명완료

선택정렬 재귀

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

• 재귀를 통해 반복적으로 배열의 뒷 부분을 정렬
• 원리는 같다. 시간복잡도 O(N^2)

선택정렬 재귀의 증명

입력 집합 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[1] < a[2] < ... < a[n-1]), n일 때 sort 함수가 성공한다. (함수가 끝날 때 a[0] < a[1] < a[2] < a[n-1] 성립)'
• -> n-1 일 때 성공한다고 가정하면, 마지막엔 최소값이 m에 해당하여 들어가 있으므로 성립된다.
• 물론 최소값을 찾는 과정의 증명도 필요하겠지만 그것까지 증명하게 되면 너무 길어지므로 이 정도만 이해하자.

- 증명완료