[ 자료구조 ] 배열 (Selection Sort, Recursive Selection Sort)

Selection Sort의 알고리즘 로직은 다음과 같다.

 

배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다.

그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다.

그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다.

 

int sort (int a[], int n) // n 은 배열의 크기
{
	//m 최소값 인덱스, t 는 교환할때 활용
    int i, j, m, t;
    for (i = 0; i < n; i++) {
         m = i ;
        for ( j = i ; j < n; j++) // j는 i 부터 n 까지 최소값 인덱스
            if (a[m] > a[j] ) m = j;
       t= a[i]; a[i] = a[m]; a[m]=t; // 두 값의 교환
    }
    return;
}

 

먼저 코드를 보자면 첫번째 루프에서 0부터 n 까지 돌아가는데 거기서 최소값을 찾아서

m에 저장한다. 그리고 그 안에서 한번 더 루프가 돌아가는데 j 는 i 부터 n 까지 가장 작은 값을 찾아서

m에 그 값을 저장하게 된다. 그렇게 해서 결과적으로 찾은 a[m] 값을 a[i] 에 저장하게 된다. 

 

 

Proof of Correctness of Sorting

• Sorting이 됐다는 증명을 어떻게 할까?
• 입력 : a[0], a[1], ... , a[n-1] <- (정수) 집합
• Sorting이 완료된 후 다음이 만족 되어야 한다.
  • Sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1], ... , b[n-1] 라고 부르자(같은 배열이지만 구별하기 위햇 이름만 다르게 부름)
  • 조건 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 Invariant

• 집합 조건을 깰 수 있는 코드는 없음. (값을 교환하거나 읽는 코드 밖에 존재하지 않기 때문)
• Prove Invariant by induction
  • Base : k = 0 일 때 (1)은 null condition 이므로 true, (2)도 null condition, true 이다. (**null condition : 아무것도 없어서 만족시켜야 할 것이 없다. 라는 뜻)
  • Step : k번째 루프가 끝났을 때, invariant가 성립한다면 k+1번째 루프가 끝났을 때도 invariant가 성립한다.
• Invariant :  k-1 번째 루프가 끝난 후에 
  • (1) a[0] < a[1] < .... < a[k-1] 
  • (2) a[k-1] < a[x] if x > k-1 
• a[k], .... , a[n-1] 중 최소값을 a[k]로 옮겼음!
• Invariant :  k 번째 루프가 끝난 후에 
  • (1) a[0] < a[1] < .... < a[k-1] < a[k]
  • (2) a[k] < a[x] if x > k

 

그렇다면 재귀적으로 Selection Sort 를 구현 하면 어떤식으로 나올까?

 

다음과 같이 코드가 나올 것이다.

 

int sort (int a[], int n) // n 은 배열의 크기
{
    int i, j, m, t;
    m = 0
    for (i = 0; i < n; i++) {
            if (a[m] > a[j] ) m = j;
    }
 
    t= a[0]; a[0] = a[m]; a[m]=t; // 두 값의 교환
    sort(a+1, n-1);
    return;
}

Proof by Induction

• 집합 조건을 깰 수 있는 코드는 지금도 없음
• Base: n=1. 할 일이 없다.
• Step:
  • n-1 일 때 sort() 함수가 성공한다면 n일 때 sort() 함수가 성공한다.
  • 즉, 재귀호출이 끝난후 a[1]<a[2]<...<a[n-1] 이라면 함수가 끝날 때 a[0] < a[1] < a[2] < ... < a[n-1] 이 성립. 

n-1 일 때 sort() 함수가 성공한다면, a[1] < a[2] <...<a[n-1] 이다. 그렇다면 이제 n 일때 sort() 하면 a[0] < a[1] < a[2] < ... < a[n-1] 임을 보여주면 되는데 a[0] < a[1] 일까? 이것은 당연히 성립할수 밖에 없다. n-1 일때 sort했을 때 우리는 일 작은 값을 a[1]으로 이동하였고, 그게 제일 작은 값임을 알고 있다. 그렇다면 n-1 재귀호출하기 전에 n에서 sort했을때는 a[0] 에 있는 값이 a[1] 보다 작은 값이 맞다. 이 과정에서 집합 조건을 깨는 코드는 없다. (단순히 값의 교환 순서만 바뀌므로)

따라서 n개일 때 모든 sort 함수가 성공하게 된다.

 

이제 시간 복잡도를 살펴보자

 

The Complexity

 

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

따라서 등차 수열로 T(n) = O(n^2) 가 된다