Selection Sort , Merge Sort, 그리고 증명

Sotring 에 대한 증명 방법

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

- Sorting 이 완료된 후 다음이 만족되어야 함

   - Sorting 이 끝난 후 배열에 저장된 값들을 b[0], b[1], ..., b[n-1] 이라고 부르자

   - 조건 1: a 배열과 b 배열의 값들은 집합으로 같음

   - 조건 2 : b[0]<b[1]< ... < b[n-1] (편의상 같은 값은 없다고 가정)

 

Selection Sort (선택 정렬) : 데이터를 하나씩 비교해서 작은값/큰값 을 앞으로 가져오고 남은 구간들에 동일한 작업을 해서 정렬하는 알고리즘. 즉, 배열에서 가장 작은 값을 앞으로 가져오는 작업 반복.

 

* Selection Sort in C (iterative process)

void selectionSort(int a[], int n){
    int i, j, t;
    for(i=0; i<n-1; i++){
    	for(j=i+1; j<n; j++){
        	if(a[j]>a[i]){
            	t=a[j]; a[j]=a[i]; a[i]=t;
                //a[i] = a[i]^a[j];
                //a[j] = a[i]^a[j];
                //a[i] = a[i]^a[j];               
            }
        }
    }
}            

시간복잡도(Complexity): $O(n^2)$ (n 까지 for 문을 n 번 돌기 때문)

 

Selection Sort 증명 by Invariant

- 조건 1 : 집합 조건을 깰 수 있는 코드는 없다. 값들은 가지고 교환만 함.

- 조건 2: Proof Invariant by Induction

  - invariant : k 번째 루프가 끝난 후에

     (1) a[0]<a[1]<...<a[k-1]

     (2) a[k-1] < a[x] if x>k-1

  - (Base) k=0 일 때 아무 루프도 돌지 않음. null condition. 만족시켜야할 게 없다.

  - (Step) k 번째 루프가 끝났을 때 invariant 가 성립하다면, k+1 번째 루프가 끝났을 때도 성립한다.

 

invariant 1: k 번째 루프가 끝난 후

 - (1) a[0]<a[1]<...<a[k-1]

 - (2) a[k-1]<a[x] if x>k-1

invariant 2: k+1 번째 루프가 끝난 후

 - (1) a[0]<a[1]<...<a[k-1]<a[k]

 - (2) a[k]<a[x] if x>k

 

k 번째 루프가 끝난 후에 남은 값들 a[k], ..., a[n-1] 중 최소값을 a[k] 로 옮김.

=> a[k] 는 invariant 1 의 'a[x]' 안에 있던 값으로 a[0]~a[k-1] 보다 클 수밖에 없고, 최소값을 옮긴 것이니 남은 a[k+1},...,a[n-1] 의 값들은 모두 a[k] 보다 큰 값!

 

invariant 는 알고리즘이 끝나서도 성립해야 함으로, 모든 루프가 끝났을 때

(1) a[0]<a[1]<...<a[n-1]

(2) a[k-1] < a[x] if x>k-1

임을 통해 invariant 가 성립함을 알 수 있다.

 

 

* Selection Sort in C (recursive process)

int selectionSort(int a[], int n){
	int i, m, t;
    m=0;
    if(n==1) return;
    for(i=0; i<n; i++){
    	if(a[m]>a[i]) m=i;
    }
	t=a[0]; a[0]=a[m]; a[m]=t;
    selectionSort(a+1, n-1);
    return;

proof by induction

- 조건 1: 집합 조건을 깰 수 있는 코드는 지금도 없음.

- 조건 2:

  - (Base) n=1 일 때, return. 수행할 일이 없음

  - (Step) 

     - n-1 일 때 selectionSort 함수가 성공한다면 (재귀적 가정. 일단 믿음)

           => 즉, a[1]<a[2]<...<a[n-1] 이라면

     - n 일 때 selectionSort 함수가 성공한다.

           => 즉, a[0]<a[1]<a[2]<...<a[n-1] 을 만족한다.

 

n일 때 재귀호출 n-1 을 한다. 이 때 n-1 의 재귀호출로 넘기는 값은 가장 작은 값 a[0] 를 뺀 (a+1) 이다.

그런데 n-1 일 때 sorting 이 완료된다는 것을 믿으니, n 으로 다시 돌아왔을 때 제일 작았던 a[0] 를 앞에 붙여주면 조건 2를 만족하게 된다. 다시 말해, 재귀호출 하기 전에 a[0] 는 나머지보다 작았기 때문에 나머지의 크기 관계(조건2) 가 만족하니 a[0] 와 합쳐도 여전히 조건 2를 만족한다는 것이다.

 

시간복잡도(Complexity): $O(n^2)$ (n 까지 for 문을 n 번 돌기 때문)

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

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

∴ T(n) = $O(n^2)$

 

 

Merge Algorithm (합병/병합 정렬) : 

 - input: 정렬된 배열 2개

 - Algorithm: 이 두 배열을 합함.

    1) 두 배열의 제일 앞을 비교해서 제일 작은 것을 새로운 배열로 옮김

    2) 남은 것들 중 앞에 두 개 비교해서 작은 것을 옮김. 이 작업을 반복.

 - output : 두 배열을 합집합만 배열을 Sorting 한 배열

 

=> 두 개씩 merge 하면서 계속 위로 올라오는 것. 그 결과는 Sorting !!

 

* Recursive Merge Sort (simple)

int mergeSort(int a[], int n){
    int h;
    int b[n];
    h=n/2;
    //copy a[] to b[]
    mergeSort(b, h);
    mergeSort(b+h, n-h);
    // b 에서 a 로 merge
    return;
}   

proof by Induction

- 조건 1: 집합 조건은 아직도 깰 수 없음. a 에서 b 로 완전히 복사되고, mergeSort 로 재귀호출할 때 b 는 b 와 b+h 의 둘로 나뉘어서 재귀적으로 집합 조건을 깨지 않는다. merge algorithm 도 역시 둘을 합집합하는 알고리즘으므로 집합 조건을 깨지 않는다.

- 조건 2:

  - (Base) n=1 일 때, 수행할 사항 없음

  - (Step)

     - n/2일 때, mergeSort 함수가 성공한다면

         => 즉, 재귀호출 후 a[0]<a[1]<...<a[n/2-1] and a[n/2]<a[n/2+1]<....<a[n-1] 을 만족한다면

     - n 일 때 emrgeSort 함수가 성공한다. 

       => 즉, a[0]<a[1]<...<a[n/2-1] < a[n/2]<a[n/2+1]<....<a[n-1] 을 만족

 

이는 귀납적으로 사실이라고 믿고 있고, 성립하는 것과 + merge Algorithm 의 정확성에서부터 알 수 있다.

 

시간복잡도(Complexity) : $O(n log n)$ 

T(n) = n + 2T(n/2)

      = n + 2(n/2 + 2T(n/4)

      = n + 2(n/2 + 2(n/4 + 2T(n/8))

      = .... = n log n

∴ T(n) = $O(n log n)$ 

 

이 식은 계속 안으로 들어가는데 T(1) 이 되면 없어진다.

이는 log n 번 내려가야 함을 의미함 (n 을 몇 번 나누면 1이 되느냐)

 

한 번의 mergeSort 함수는 (거의) n 시간으로 보면 된다. 

(copy 에 n, sort 에 각각 n/2 씩, merge 에도 n)

 

이전의 selection sort 와 비교해서 , 월등히 빠르다는 것을 알 수 있다.

 

 

시간복잡도를 정리하면 다음과 같다.

Algorithm	Complexity
selection sort (iterative)	$O(n^2)$
selection sort (recursion)	$O(n^2)$
merge sort (recursion)	$O(n log n)$