[자료구조] Selection Sort 증명

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

 

선택정렬에 대하여 증명하였다. 알고리즘에 관한 증명들을 먼저 알려주시고 있는데, 이후에 연결리스트나, 스택 등을 설명해주신다 하셨다.

 

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]

 

Selection Sort 의 증명

선택 정렬의 경우에 Invariant로 증명할수가 있다. 다음 코드를 먼저 확인해 보자.

inline void swap(int& x, int& y){
	int temp = x;
	x = y;
	y = temp;
}

void selectionSort(int a[], int n)
{
	for(int i = 0; i < n-1; i++){
		int least = i;
		for(int j = i+1; j < n; j++)
			if(a[j] < a[least]) least = j;
		swap(a[i], a[least])
	}
}

 

수업때 보여주신 코드와는 조금 다르게 구현하였다.

 

이를 Invariant를 사용하여 증명해 보자. 아 Invariant가 무엇인지 부터 말하고 시작해야겟다.

Invariant: 단어 의미 그대로 불변하는 조건이다. 이 불변의 조건이 함수가 도는 동안 변화가 없으면 증명되는 것 이다.

 

선택정렬 에서는 Invariant를 다음과 같이 정하자.

▶ 집합 조건을 깰수 있는 코드는 없다.

▶ Invariant: k번째 loop가 끝난 후에는

(1) a[0] < a[1] < ... < a[k-1] 이 성립한다.

(2) 만약 x > k-1 이라면 a[x] > a[k-1] 이 성립한다.

이를 그림으로 확인하면 다음과 같다.

(3) invariant가 성립하면 n번째 loop가 끝났을때 k = n이 되고, a[0] < a[1] < ... a[n-1]이 된다. 즉 sorting 되었다.

위의 invariant가 함수가 동작하는 동안 항상 유지되어야 한다.

 

이제 귀납법으로 증명해 보자.

 

(1) Base: P(1)이 참임을 보여야 한다.

k가 1이면 위의 Invariant 조건(1) 에서 a[0] < a[1-1] 이 되니 null condition이다. 성립할 조건이 아예 없으니 true이다.

Invariant 조건(2)의 경우 a[0] < a[x]가 된다. 즉

 

a[0] < a[1]

a[0] < a[2]

~

a[0] < a[n-1]

 

을 만족하게 된다. true이다.

Invariant는 성립한다.

 

(2) Step: P(n-1) -> p(n) 이 참임을 보여야 한다.

 

수학적 귀납법에 의해 P(n-1)이 사실이라 믿으면

inavariant (1) a[0] < a[1] < ... a[k-1] 가 성립하며

inavariant (2) 만약 x > k-1 이라면 a[x] > a[k-1] 이 사실이다.

 

즉, k번째 loop가 끝난후에는

a[k+1] ... a[n-1]중 최소값이 a[k]로 옮겨지고, 이는 알고리즘에 의해서 사실인 내용이다.

 

k+1 번째 loop가 끝난 다음에

inavariant (2) 만약 x > k 이라면 a[x] > a[k] 이 성립한다. 왜냐하면 최소값을 a[k]로 옮겼기 때문이다.

inavariant (1) 은 a[0] < a[1] < ... a[k-1] < a[k] 가 성립함을 보여야 하는데, 이미 P(n-1)의 귀납적 사실에서

a[0] < a[1] < ... a[k-1] 가 사실임을 알고있었다. a[k-1] < a[k] 만 보이면 끝이난다.

a[k]는 사실 자리가 옮겨지기는 했지만 옮기기 전에는 P(n-1)의 사실중 하나인 if x > k-1 이면 a[k-1] < a[x] 에서 a[x]에 해당한다. 

따라서 a[k-1] < a[k]임을 보였고, 증명이 완료된다.

Invariant는 성립한다.

 

(3) Result: P(n)은 모든 자연수 n에 대해서 참이다.

 

Complexity

​