250910 - insertion sort: correctness

알고리즘 과제를 받았다.

일단 과제를 수행하기 전에 자료로 주신걸 먼저 이해하는게 중요하다고 생각했다.

시작해보겠다.

 

induction(귀납법)

모든 경우에 대해 특정 성질을 만족한다는 명제를 증명하는 방법이다.

1) i = 0 일 때 Ai 가 성립한다.

2) Ai-1이 성립할 때 Ai 도 성립한다.

3) 모든 i >= 0 의 경우, Ai 가 성립한다.

 

예를 들어.. i = 1 이라면?

i = 0 이니 A0 이 성립한다.

A0 이 성립하니 A1 도 성립한다.

 

i = 3이라면?

i = 0 이니 A0 이 성립한다.

A0 이 성립하니 A1 도 성립한다.

A1 이 성립하니 A2 도 성립한다.

A2 이 성립하니 A3 도 성립한다.

 

insertion sort

삽입정렬 : 

#include<vector>

void insertionSort(std::vector<int> nums){
	for(int i=0;i<nums.size();i++){
        int j=i;
        while(j>0 && nums[j-1] > nums[j]){
            int tmp = nums[j];
            nums[j] = nums[j-1];
            nums[j-1] = tmp;
            j--;
        }
    }
}

 

나의 주장 : i번째 루프를 돌고 나면, nums[0, ..., i] 번째까지 정렬이 되어 있을 것이다.

증명 : 귀납법으로 한다.

먼저, i = 0 일 때 nums[0] 는 1개의 숫자 뿐이므로 정렬되어있다.

귀납법에 의해, 내가 i 번째 ( i > 0 ) 반복을 시작할 때 nums[0, ..., i-1] 은 정렬되어 있을 것이다.

//이미 지나온 것들은 당연히 정렬이 되어있겠지..

 

while 문의 시작인 nums[i] 를 n 이라고 하자.

while 문은 j = 0 (가장 왼쪽인 경우) 또는 nums[j-1] <= n (내가 지금 보고 있는 값보다 작거나 같은 숫자를 만난 경우) 에 멈춘다.

//즉 가장 왼쪽이 아니고 && 내가 지금 넣으려고 하는 값보다 큰 숫자를 만나면? 둘이 바꾼다 -> 큰 애를 뒤로 보내!

n은 nums[j] 를 저장하고, nums[0, ..., j-1] 의 숫자들은 n 보다 작거나 같을 것이고, nums[j+1, ..., i] 의 숫자들은 n보다 클 것이다.

//내가 원래 보고 있던 것, 즉 n는 나보다 큰 값을 만나면 계속 앞으로 한 칸 가고 밀림

따라서 nums[0, ..., i] 는 inner 루프를 돈 이후 정렬된다고 볼 수 있다.

 

이제 내일은 선택정렬 해야된다..