Selection Sort(선택정렬)과 증명

Selection Sort

Selection Sort은 가장 기본적인 정렬 알고리즘 중 하나이다.

알고리즘의 진행 순서는 다음과 같다.

1. 주어진 리스트에서 최소값을 찾는다.
2. 그 값을 맨 앞의 값과 교체한다.
3. 맨 처음위치를 뺀 나머지 리스트에 대하여 반복한다.

 

그림으로 보는게 가장 이해가 잘 될 것같다.

출처: 위키피디아

테이블로 보면 다음과 같다.

Round	Array	Min Value
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

 

시간복잡도

위의 테이블 예시를 보면 n = 8인 array에서 index가 0부터 n-1까지 n번 기준으로 설정되고 그 값을 기준으로 array의 나머지 값의 비교가 n-1,n-2, n-3 ...1번 반복된다. Big-o notation으로 계산하면 기준이 $O(n)$번 설정되고 각 기준마다 최대 $O(n)$ 번 비교를 수행하기 때문에 시간복잡도는 $O(n^2)$이된다.

 

구현 - for loop을 이용한 구현

 

구현 - 재귀를 이용한 구현

 

 

증명(Proof)

Selection Sort역시 귀납법을 통해 증명할 수 있다.

 

1. Proof by Invariant

• 집합 조건을 깰 코드는 없다.
• k번째 루프가 끝나면
  • 1) a[0] < a[1] <...<a[k-1]이다.
  • 2) x > k-1이면 a[k-1] < a[x]이다.

1-2. Invariant에 대한 수학적 귀납법을 통한 증명

• Base: k=0이면 아무것도 없기 때문에 true이다.
• Step: k번째 루프가 끝났을 때 invariant가 성립한다면 k+1번째 루프가 끝났을 때도 Invariant가 성립한다.

1. Invariant: k번째 루프가 끝난 후에
   1. a[0] < a[1] <...< a[k-1]
   2. a[k-1] < a[x] if x > k-1
2. Invariant: k+1번째 루프가 끝난 후에
   1. a[0] < a[1] < ... < a[k-1] < a[k] (a[k-1]보다 큰 값중 가장 작은 값이 a[k]에 들어가기 때문에)
   2. a[k] < a[x] if x > k

따라서 Invarian가 성립한다.

 

2. 정확성 증명 (Proof of Correctness of Sorting)

Sorting 됐다는 것을 어떻게 증명 할 수 있을까?

Sorting이 완료된 후라면 다음이 만족해야한다.

• Sorting이 끝난 후 배열에 저장된 값들을 b[0],b[1]...b[n-1]이라고 지칭하면
• 조건1. 집합 {a[0],a[1],...,a[n-1]} = {b[0],b[1]...,b[n-1]}이 성립한다. 집합은 순서가 없기 때문이다. 즉, a와b는 같지만 순서만 다른 배열이라는 뜻이다.
• 조건2. b[0] < b[1] < ... <b[n-1]이 성립한다. (편의상 같은 값은 없다고 가정)

2-1. 정확성에 대한 수학적 귀납법을 통한 증명

• 집합 조건을 깰 수 있는 코드는 없다. (array 안에서 순서만 변한다)
• Base: n=1 이때는 할 일 이없다. (원소 하나를 sorting할 수는 없다)
• Step
  • index=1일때 Selection_Sort()함수가 성공하면(재귀 기준) a[1] < a[2] < ... < a[n-1]이다.
  • index=0일때 Selection_Sort()함수가 성공하면 a[0] < a[1] < ... < a[n-1]이 성립한다.