[ 알고리즘 ] 정렬(1) : Selection Sort, Recursive Selection Sort

1. sorting의 조건

 

정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다.

 

조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다.

조건2. 배열 b는 b[0]<b[1]< ... < b[n] 이어야한다. (같은 값은 없다고 가정)

 

위 두 조건이 성립한다면 그 배열은 정확하게 sorting 되었다고 말 할 수 있다.

 

2. Selection Sort

Selection Sort

위 코드는 선택정렬 코드이다.

 

아이디어는 최소값을 찾아 맨 앞에 배치하는 것이다.

 

간단하게 설명해보자면, i는 현재 탐색할 인덱스 번호이고 j는 i와 비교할 인덱스 번호이다.

i와 j를 비교하여 가장 작은 값을 i에 배치한다. 

m 은 최소값을 담고있는 변수이다.

 

그렇게 하다보면 i 앞에는 정렬이 완료되어있다고 볼 수 있다.

 

증명 (proof by Invariant)

 

invariant : k 번 째 루프가 끝나면 a[0]<a[1]< ... < a[k-1] 이 성립하고 k-1 < x 에 대해서 a[k-1] < a[x]가 성립한다.

위 invariant가 성립한다면 sorting 조건을 성립하게된다. 

 

증명 (proof by Induction)

위 invariant를 수학적 귀납법으로 증명해볼 것이다.

 

Base : k=0 일 때 할 일이 없다

Step : k 번째 루프가 성립한다면 k+1번째 루프도 성립

 

k번째 실행 후 a[0]<a[1]< ... < a[k-1] 

             ↓

a[k] ... a[n-1] 중 가장 작은 값을 a[k]로 이동

             ↓

k+1 번째 실행) a[0]<a[1]< ... < a[k] 실행  

 

 

3. Recursive Selection Sort

Recursive Selection Sort

 

위 코드를 간단하게 설명해보자면,

들어온 배열의 맨 앞 값을 m으로 설정하고 a[1] 부터 쭉 비교하면서 최소값을 찾는다.

그 최소값을 a[0]과 교체한다.

그러고 다시 sort를 호출하는데, 이미 맨 앞은 최소값을 왔으므로 a+1를 sorting 하도록 인자로 넘겨준다. 

 

증명 (proof by Invariant)

invariant :

조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다.

조건2. 배열 b는 b[0]<b[1]< ... < b[n] 이어야한다. (같은 값은 없다고 가정)

 

swap만 이루어지지 배열 내용을 바꾸는 코드는 없으므로 조건1은 성립한다.

 

증명 (proof by Induction)

위 invariant의 조건2 를 수학적 귀납법으로 증명해볼 것이다.

 

Base : n=1 이면 return (코드에는 없다)

Step : n−1 일 때 sort 함수가 성공한다고 가정하자. 

          항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다.

          따라서  재귀로 들어가기 전부터 ∀x((x>0)→(a[0]<a[x])) 가 성립했다.

          그러므로 n일 때 a[0]<a[1]<a[2]<...<a[n−1] 이므로 sort 함수가 성공한다.

 

3. Recursive Selection Sort Complexity

 

T(n) = n+T(n−1)

       = n+(n−1)+T(n−2)

       = ... = O(n2)