용어
배열 A는 배열 B의 서브 배열이다 : $a \in A, b \in B, A \subseteq B, |A|<|B|$
배열은 Set이 아닌, Sequence이다. (원소 간의 자료 중복 허용, 순서가 존재)
Selection Sort 증명
sort() 함수가 하는 일 :
함수 sort()는 길이가 n인 배열 a에서 가장 작은 값의 위치를 찾는다.
for loop 안에서,
base : $j = 0$ (첫 번째 반복)
배열의 모든 값은 0보다 큰 양수이므로, 배열의 첫 번째 인덱스에 있는 값은 항상 0보다 크므로, m에는 0이 저장된다. ⇒ TRUE
step : $j = k$
이전 루프동안 올바르게 실행되었다면 $a[m]$이 $a$배열의 0번부터 $k - 1$번째 서브 배열의 원소 중 최솟값을 저장한다.
만약 $a[k]$가 $a[m]$보다 작다면, $m$의 값은 $k$가 된다. (가장 작은 값을 가르키는 포인터 인덱스가 $k$가 되는 것이다)
만약 $a[k]$가 $a[m]$보다 크거나 같다면, 변화가 없다.
즉, $a[k]$는 $0$번부터 $k - 1$번째 서브 배열의 최솟값보다 작으로, $a[x] > a[k], (x\in{ x| 0 \leq x \leq k - 1, x \neq k })$ 가 성립한다.
위의 분기에서 매 step마다 작은 값의 인덱스를 $m$으로 갱신하므로 ⇒ TRUE
for loop가 종료된 후,
배열 a에서 가장 작은 값인 $a[m]$이 배열 a의 0번째 인덱스 위치에 오게 된다.
이때, 배열 a의 0번째 인덱스 위치에 있던 값과 swap되므로, 집합 조건은 깨지지 않는다.
이후, sort() 함수에는 매개변수로 a 배열의 서브 배열이면서, 길이가 1 작고, 0번째 인덱스 값이 빠진 서브 배열이 전달된다.
base : $n=1$ ⇒ TRUE
step : 이때, 위 의 과정과 sort() 함수가 성공적으로 작동한다고 가정했을 때,
sort() 함수 호출 전에 배열 a에서 가장 작은 값이 배열의 0번째 인덱스에 위치한다.
위 증명에 의해, $a[0] < a[x], (1 \leq x < n)$이 성립한다.
다음에 호출되는 sort() 함수는 배열 a의 서브 배열을 매개변수로 받는다.
sort()가 호출되고 난 후,
1) $a[0] < a[x], (1 \leq x < n), a[1] < a[y], (2 \leq y < n)$이 성립
2) $a[1] \in { k | a[x], 1 \leq x < n}$이므로, $a[0] < a[1]$이 성립
즉, $a[0] < a[1] < a[x], (2\leq x < n)$이 성립 ⇒ TRUE
즉, 정렬되기 전 배열인 $a$, 정렬된 후의 배열을 $a'$라고 할 때,
1) ${a'[0], a'[1], ..., a'[n-1]}={a[0], a[1], ..., a[n-1] }$으로, 집합 조건은 성립한다.
2) 위에서 증명한 것과 같이 함수가 완전히 종료되면 $a[0]<a[1]<...<a[n-1]$이 성립한다.
시간복잡도
어떤 스텝에서,
for loop : $O(N)$
다음 sort() 함수를 호출할 때, 인자값은 $n-1$이 전달된다.
n == 1인 경우 종료되므로, 함수는 재귀적으로 $N$번 호출된다.
즉, $sort(N) ⇒ O(N) + sort(N - 1) => O(N) + O(N-1) + sort(N-2) => ...$
$sort(N) = N * O(N)=O(N^2)$
Merge Sort 증명
Merge가 하는 일
정렬된 두 배열을 합치며 정렬한다.
base : $N = 0$ ⇒ TRUE
step : $k$번째 스텝일 때,
merge된 배열 a의 $k-1$번째 인덱스까지는 정렬이 되었다고 가정,
두 배열 b1과 b2에서 a로 insert 된 마지막 값 다음 인덱스의 값을 $x_1$, $x_2$라고 할 때, 다음이 성립.
$t\in a \Rightarrow x_1>t, x_2>t$
만약 $t_1>t_2$라면, 배열 a에 $x_2$를 insert한다. → b2의 $x_2$ 다음 값이 $x_2$로 갱신되며, 여전히 $t\in a \Rightarrow x_1>t, x_2>t$가 성립한다. 반대의 경우도 마찬가지이다.
즉, $t\in a \Rightarrow x_1>t, x_2>t$이 성립한다. ⇒ TRUE
즉, 모든 스텝이 종료된 후, 배열 a는 정렬된 상태이다.
base : $N = 1$ ⇒ TRUE
step : $k = n / 2$ 스텝일 때, sort() 함수가 성공한다고 가정하면
배열 b의 서브 배열이고, 인자로 인덱스 0번째부터 n / 2 - 1번째까지 가지는 배열을 호출한 sort()에 의해
$b[0] < b[1] < ... < b[n / 2 - 1]$
배열 b의 서브 배열이고, 인자로 인덱스 n / 2번째부터 n - 1번째까지 가지는 배열을 호출한 sort()에 의해
$b[n/2]<b[n/2+1]<...<b[n-1]$이 성립한다고 가정
이후, Merge가 정확하게 동작한다면, 정렬된 두 배열을 정렬해서 반환하므로,
함수가 끝날 때 merge된 배열 a는 $a[0]<a[1]<...<a[n/2-1]<a[n/2]<a[n/2+1]<...<a[n-1]$이 성립한다.
시간복잡도
어떤 스텝에서,
배열 복사 : $O(N)$
Merge 알고리즘 : $O(N)$
sort() 함수를 호출할 때, 전달되는 배열의 길이는 $n / 2$, sort() 함수가 두 번 호출된다.
N == 1인 경우 종료되므로, 다음으로 전달된 인자인 n / 2가 n / n이 되어 1이 되려면 $\log N$번 호출된다.
즉, $sort(N) \Rightarrow 2O(N) + 2sort(N/2) \Rightarrow 2O(N)+2(n/2+2sort(n/4)) \Rightarrow ...$
$sort(N)=O(N \log N)$ (상수 시간 무시)
