[Algorithm] 2. Getting Started

 

1. insertion sort

 insertion sort는 sorting problem을 푸는 한 가지 알고리즘이다. sorting problem의 input은 \(n\)개 수로 이루어진 수열 \(\langle a_1, a_2, ..., a_n\rangle\)이고, output은 \(a_1'\leq a_2' \leq ... \leq a_n'\)을 만족하는 재배열 수열 \(\langle a_1', a_2', ..., a_n'\rangle\)이다. insertion sort는 작은 수의 원소를 정렬하는 데 유용하다.

 

 insertion sort는 input에서 각 인덱스에 있었던 원소가 지금까지 앞에서 정렬된 원소들 중 어디에 들어가야 할지 결정하고 나머지를 shift한다. insertion sort의 pseudocode는 다음과 같다.

 

INSERTION-SORT(A)

for j = 2 to A.length
	key = A[j]
	i = j - 1
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i + 1] = key // we perform i = i - 1 and break, so use i + 1 again

 

 이 알고리즘이 correct하다는 것을 증명하기 위해서는 loop invariant을 찾으면 좋다. loop invariant는 반복문에 대하여 유지되는 성질인데, initialization, maintenance, termination의 세 조건을 만족해야 한다. initialization은 첫 반복문을 시작하기 전에 해당 성질을 만족해야 함을 의미한다. maintenance는 어떤 iteration을 시작하기 전에 해당 성질을 만족하면 iteration을 끝내도 그 성질을 만족해야 함을 의미한다. termination은 반복문이 종료되었을 때 loop invariant가 이 알고리즘이 correct하다는 것을 보여주는 데 유용해야 함을 의미한다.

 

 insertion sort에서 loop invariant는 \(\texttt{A[1..j-1]}\)이다. 다음 과정을 따를 수 있다.

• initialization: \(\texttt{j=2}\)일 때 iteration을 시작하기 전에, \(\texttt{A[1]}\)는 자명하게 첫 번째 인덱스에 있고, 정렬되어 있다.
• maintenance: \(\texttt{A[j]}\)는 iteration이 끝난 후 \(\texttt{1..j}\)의 인덱스 안에 들어 있게 되고, \(\texttt{A[1..j-1]}\)도 최대 1칸만 shift 되므로 \(\texttt{1..j}\)의 인덱스 안에 들어 있다. 또한, \(\texttt{A[1..j-1]}\)이 정렬되어 있었다면, iteration 후 \(\texttt{A[1..j]}\)도 정렬되어 있다.
• termination: \(\texttt{A.length}\)까지 iteration이 끝나면 \(\texttt{A[1..n]}\)이 정렬되므로, sorting problem을 correct하게 푼다.

 

2. 알고리즘 분석

 알고리즘 분석을 할 때는, 각 줄의 cost를 계산해야 한다. insertion sort의 경우 다음과 같이 계산할 수 있다.

 

INSERTION-SORT(A)

• line 1: \(c_1 \times n\)
• line 2: \(c_2 \times (n-1)\)
• line 3: \(c_3 \times (n-1)\)
• line 4: \(c_4 \times \sum_j t_j\)
• line 5: \(c_5 \times \sum_j (t_j-1)\)
• line 6: \(c_6 \times \sum_j (t_j-1)\)
• line 7: \(c_7 \times (n-1)\)

 여기에서, \(t_j\)는 각 \(j\)에 대하여 while문의 조건이 실행되는 횟수이다. 마지막 한 번은 조건을 만족하지 않아 break되므로 실제 while문 내부가 실행되는 횟수는 1씩 줄어듦에 유의하라.

 

 best case는 가장 비용이 작은 경우로, \(t_j=1\)이 항상 성립하는 경우이다. 또한, worst case는 가장 비용이 큰 경우로, \(t_j=j\)이 항상 성립하는 경우이다. insertion sort의 경우 best case는 linear function, worst case는 quadratic function이다. 앞으로 worst case를 중점적으로 읽을 것이나, 확률론적 분석에서는 average case를 분석하기도 할 것이다.

 

3. 알고리즘 디자인

 insertion sort는 정렬된 원소의 수를 하나씩 증가시키는 incremental approach를 사용했다. 이와 다른 접근 방식으로 divide and conquer approach가 있다. 이 방법은 사실 divide, conquer, 그리고 combine의 세 단계로 이루어져 있다.

• divide: 문제를 여러 개의 subproblem으로 나눈다.
• conquer: subproblem을 재귀적으로 해결한다.
• combine: subproblem의 답을 활용하여 원래 문제를 해결한다.

 이 방법을 사용하는 대표적인 알고리즘은 merge sort 알고리즘이다. 다음 세 단계를 따른다.

• divide: 배열을 두 개의 \(n/2\) 크기의 subarray로 나눈다.
• conquer: subarray 두 개를 각각 정렬한다.
• combine: 정렬된 subarray를 merge하여 원래 배열을 정렬한다.

 combine 과정에서 사용되는 함수는 MERGE(A, p, q, r)이다. \(\texttt{A[q+1..r]}\)이 이미 정렬되어 있을 때, additional array를 만들어 저장한 후 각 subarray의 순서는 유지한 채 재배열하여 \(\texttt{A}\)를 정렬한다.

 

MERGE(A, p, q, r)

n1 = q - p + 1
n2 = r - q
let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays
for i = 1 to n1
	L[i] = A[p + i - 1]
for j = 1 to n2
	R[j] = A[q + j]
L[n1 + 1] = inf
R[n2 + 1] = inf
i = 1
j = 1
for k = p to r
	if L[i] <= R[j]
		A[k] = L[i]
		i = i + 1
	else A[k] = R[j]
		j = j + 1

 

 이 경우 loop invariant는 각 iteration에서 \(\texttt{A[p..k-1]}\)이 \(\texttt{L[1..n1+1]}\)과 \(\texttt{R[1..n2+1]}\) 중 가장 작은 \(\texttt{k-p}\)개의 원소를 순서대로 저장한다는 것이다.

 

 divide and conquer 알고리즘의 cost는 재귀적으로 계산한다. 다음은 merge sort 알고리즘의 cost이다.

• divide: \(\Theta(1)\)에 나눌 수 있다.
• conquer: 두 개의 \(n/2\) 크기 subarray로 나누므로 \(T(n/2)\)이다.
• combine: 두 배열을 합치는 데 \(\Theta(n)\)이 걸린다.

 따라서 다음 식이 성립한다. \[T(n)=\begin{cases}\Theta(1) & (n=1) \\ 2T(n/2)+\Theta(n) & (n>1)\end{cases}\]

 이 recursion 식을 푸는 방법 중 하나로 recursion tree를 그리는 방법이 있다. recursion tree의 각 level에 대하여 총 cost를 구하고, level의 cost를 모두 더하는 방식으로 구할 수 있다.

 

4. 문제 풀이

 먼저, 수학적 귀납법을 통해 \[T(n)=\begin{cases} 2 & (n=2) \\ 2T(n/2)+n & (n=2^k, k>1)\end{cases}\]의 cost가 \(T(n)=n \lg n\)임을 보이자. \(n=2\)인 경우 \(T(2)=2=2 \times \lg 2\)가 성립한다. \(n=2^k\)인 경우 \(T(2^k)=kn\)이라 가정하자. 그러면 \(n=2^{k+1}\)인 경우 \(T(n)=2T(n/2)+n=n+2 \times k(n/2)=n(k+1)=n \lg n\)이 성립한다.

 

 다음으로, bubblesort가 correct함을 보이자.

 

BUBBLESORT(A)

for i = 1 to A.length - 1
	for j = A.length downto i + 1
		if A[j] < A[j - 1]
			exchange A[j] with A[j - 1]

 

 bubblesort가 correct함을 보이기 위해서는 코드 수행 후 \(A'[1] \leq A'[2] \leq ... \leq A'[n]\)을 만족해야 하고, 각 원소들이 원래 원소들의 재배열이어야 한다. 이때, bubblesort의 nested loop의 loop invariant는 \(\texttt{A[j-1..n]}\) 중 \(\texttt{A[j-1]}\)이 가장 작은 원소라는 것이고, 가장 바깥쪽 loop의 loop invariant는 원래 배열에서 가장 작은 \(\texttt{i}\)개의 원소를 순서대로 저장하고 있다는 것이다. bubblesort의 worst case running time은 \(\Theta(n^2)\)으로 insertion sort와 같다.