selection sort 증명

[proof by Loop Invariant]

가설 : P(n)은 정렬되어 있다. => a[0] < a[1] < ... < a[n] 이 성립한다. 

 

초기 단계: n = 0일때, 크기가 0이므로 가설 성립. 

 

base : n = 0일때, 크기가 0인 배열이므로 가설이 성립한다. 

step :

P(n)이 참일때 => a[0] < a[1] < ... < a[n] 으로 정렬되어 있다. --> (즉 for (int i = 0; i < n + 1; i++) 에서 i = n까지 돌았을때)

P(n+1)이 참이다. --> 정렬된 P(n)의 최댓값보다 큰 값을 선택 -> P(n)이 정렬한 배열 뒤에 붙임 --> 최댓값보다도 큰 값을 붙였으므로 P(n+1)은 정렬되어 있다는 가설을 깨지 않음. 

 

terminate : n이 배열 크기 끝까지 도달했다는 terminate 종료 조건에 도달함. 

따라서 n까지는 모두 정렬되어 있음이 보장됨.

 

++

처음에는 induction인가? 하며 헷갈렸는데, 쓰고 보니 너무 명백한 loop invariant이다. 심지어 대표적인 경우처럼 보이기도 한다. 그렇다면 진정 induction과 loop invariant의 차이점은 무엇인가 ...