1-(2) Getting Started-(i) Insertion Sort

이 챕터는 알고리즘의 대표적인 문제인 Sorting problem을 통해 이 책 전체의 framework를 제시하는 챕터라고 한다. 그냥 예제를 통해 책의 서술 방법을 말하는 챕터.

 

Sorting problem은 다음과 같이 정의되는 문제이다. (대부분의 알고리즘 문제가 아래와 같은 형식으로 정의된다.)

Input: n 개의 연속되는 수들 a₁, ...., a_n

Output:a1, ...., an 가 특정 순서에 대해 정렬된 수의 나열 a'₁, ...., a'_n

이 Sorting problem을 푸는 방법을 Insertion sort와 Merge sort를 통해 제시하고 있다.

 

(1) insertion Sort(삽입 정렬)

책에 나와있지는 않지만 insertion sort는 incremental algorithm이라는 카테고리에 속하는 알고리즘이다. Incremental algorithm이란 j번째 input을 볼 때 1번째부터 j-1번째까지는 이미 부분적으로 해의 성질을 만족하게 하는 알고리즘이다.

또한 Insertion Sort는 in-place알고리즘으로서 정렬이 주어진 리스트 내에서 이루어진다. 즉, "추가적인 저장 공간"을 필요로 하지 않는다. (뒤에서 나오는 Merge Sort와의 차이점)

/*

"추가적인 저장 공간"이 필요없는 것에 대한 첨언: 추가적인 저장 공간이 필요 없다는 건 조금 엄연하지 못한 말이고 at most a constant number of place를 외부 저장 공간에 요구할 수 있음을 말한다.

*/

 

그럼 구체적으로 어떤 방법의 알고리즘인가? 앞서 말한 Incremental한 성질과 알고리즘의 이름을 생각해보면 비교적 쉽게 생각해볼 수 있는 방법이다. 만약 내가 이미 정렬된 배열에 수를 하나 넣어 정렬된 배열을 만든다고 생각해보자. 그럼 그냥 그 수보다 작은 수를 찾을 때까지 배열 끝부터 뒤져보면 된다. 왜냐하면 j-1번째까지는 배열이 정렬되어 있기 때문이다.

예를들어 1 4 9 12로 이미 정렬된 배열이 있고 10을 넣는 상황을 생각해보자. 그럼 12부터 보면 된다. 12보다는 10이 작으니까 그 이전 수를 보면 9다. 그럼 10을 그 뒤에 "삽입"하고 12를 10의 뒤로 밀면 1 4 9 10 12가 된다. 이런 것을 j=from 2 to n 반복하면 된다. <그림1>은 그런 반복적인 삽입 방법을 설명한다.

(배열의 첫번째 요소에 대해서는 할 필요X)

<그림1>: Insertion Sort의 과정[1]

교재에 제시된 pseudo code를 c++로 작성해보면 밑과 같다.

/* Implementation of Insertion sort */
#include<iostream>
using namespace std;
void insertionsort(int* arr, int size) {
	int j = 0;
	int key = 0;
	for (int i = 1; i < size; i++) { //i=0인 첫번째 원소에 대해서는 할 필요 없음
		j = i - 1;
		key = arr[i];
		while (j >= 0 && key < arr[j]) {
			//key보다 큰 놈을 shifting하는 과정
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;//shifting을 멈춘 곳의 오른쪽에 삽입
	}
}
int main() { //test case
	int arr_test[] = { 6,4,7,2,4,1,9,3 };
	int arr_size = 8;
	cout << "before sorting: ";
	for (int i = 0; i < arr_size; i++) {
		cout << arr_test[i] << " ";
	}
	cout << endl;
	insertionsort(arr_test, arr_size);
	cout << "after sorting: ";
	for (int i = 0; i < arr_size; i++) {
		cout << arr_test[i] << " ";
	}
}

출력 결과는 다음<그림2>와 같다.

<그림2: test case에 대한 insertion sort의 출력결과>

여기서 우리는 이 알고리즘의 correctness proof를 해보아야 하는데 그것은 특정 절차를 밟아서 한다. 그 전에 한가지 개념을 정의한다. 우리는 이 알고리즘에 대해 한 가지 가정을 놓고 했는데 그것은 이것이다.

"모든 j번째 loop의 시작에서 배열의 1부터 j-1번째 요소까지는 정렬되어있다." 이 가정(성질)이 항상 만족함을 보여야 정렬의 정당성이 확보된다. 따라서 다음과 같은 일반적인 개념을 정의한다.

 

*Loop Invariant: 모든 루프가 시작하는 위치에서 항상 만족하는 어떤 성질

이 Loop invariant의 참/거짓은 세 가지 절차에 대해 증명해야 한다.

(1) Initiallization: loop의 첫 iteration에서 참일 것.

(2) Maintanence: 만약 모든 루프의 출발에서 참이라면 그것은 다음 루프의 출발에서도 참으로 남을 것.

(3) Termination: loop가 종료되었을 때 참.

 

이러한 증명 절차는 고등학교에서 배운 수학적 귀납법과 매우 유사한 면이 있는데 Termination이 추가되었을 뿐이다.

이 증명을 insertion sort의 corectness proof에 적용하면 다음과 같을 것이다.

Loop Invariant: j'th loop 시작시 배열이 j-1까지는 부분적으로 정렬되어있다.

(1) Initiallization: 첫 iteration에서 이전요소까지의 배열은 정렬되어 있는가?

-> 하나의 element만을 가진 배열이므로 정렬되어있음.

(2) Maintanence: j-1번째까지 배열이 정렬되어 있을 때 해당 loop를 돌리면 j번째까지 정렬된 배열이 나오는가?

->ㅇㅇ

(3) Termination: 종료되었을 때 n까지 정렬된 배열이 나오는가?

->ㅇㅇ

 

이러한 과정을 통해 j=1부터 n까지 Loop Invariant에 해당하는 성질이 모두 참임이 보여지고 그에 따라 알고리즘 자체의correctness를 보일 수 있게된다. 알고리즘의 시간 분석과 MergeSort는 다음 게시글에서 다룬다.

 

-Reference

[1] Leiserson, Charles Eric, et al. Introduction to algorithms. Vol. 6. Cambridge, MA: MIT press, 2001.