삽입정렬( Insertion sort )

삽입정렬 ( Insertion Sort )

기본 IDEA :

배열의 원소들을 카드라고 생각하자.
정렬된 카드를 왼손에 배치한다고 생각했을 때, 정렬되지 않은 카드들을 한개씩 뽑아서 매번 적절한 위치에 배치시킨다.
이 과정을 탁자위의 카드가 한개도 남지 않을 때 까지 반복하면 결국 손에 남아 있는 카드들은 정렬 된 상태를 유지한다.

입력 :

n개의 수들로 이루어진 수열 { $a_1$, $a_2$, $a_3$, .... , $a_n$ }

출력 :

$a'_1$ $\leq$ $a'_2$ $\leq$ $a'_3$ $\leq$ .... $\leq$ $a'_n$ 을 만족하는 입력 수열의 재배치

STEP :

삽입정렬의 과정

PSEUDO CODE ( 의사 코드 ):

0. Insertion_sort( A ){
1.    for j = 2 to A.length
2.        key = A[j]
3.        i = j-1
4.        while( i >= 0 and A[i] > key )
5.            A[i+1] = A[i]
6.            i = i-1
7.            
8.        A[i+1] = key
9. }

C++ 코드 :

void insertionSort(int* arr, int size){
    int key;
    // arr의 idx 는 0부터 시작
    for(int j=1; j<size; j++){
        key = arr[j];
        int i = j-1;
        while( i>=0 && arr[i] > key ){
            arr[i+1] = arr[i];
            i--;
        }
        arr[ i + 1 ] = key;
    }
    return ;
}

해석

$A[1,...,i]$ 는 위 기본 IDEA에서 언급한 "왼손의 카드" 라고 생각하자.
1번의 for loop 안에서 i의 값은 정렬된 배열의 마지막 원소를 가리킨다( 즉, 왼손에 위치한 마지막 카드 )
while루프에서(4~6라인) 정렬된 배열의 마지막 원소부터 첫 원소까지 값을 Swap 해가며 적절한 위치를 찾는다. Swap을 하면서 한칸씩 칸이 오른쪽으로 당겨지게 된다.
위 과정을 반복하면 while 문은 $ A[0]이나 A[i] \leq key$ 를 만족하는 첫 원소에서 빠져나오게 되는데 이때 적절한 위치는 i값의 이전 위치인 i+1 인 곳이다.
해당 위치에 key를 삽입하고 정렬되지않는 원소가 하나도 남지 않을 때 까지 for loop 를 반복하면 결국 배열의 모든 원소는 정렬 된 상태로 재배치 되게 된다.

알고리즘의 정당성 확인

---

알고리즘의 정당성을 보이기 위해 "루프 불변성(loop invariant)" 를 활용해보자.

루프 불변성 : loop가 진행되어도 변하지 않는 특성이나 본질

루프 불변성을 보이기 위해서는 다음 3가지 특성을 만족해야 한다.

1\. 초기조건 : 루프가 첫번째 반복을 시작하기 전 루프 불변성이 참이여야 함.


2\. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이여야 한다.  
    _<1,2번 조건 만족시 loop가 반복을 시작할 때 루프 불변성은 항상 참이다>_


3\. 종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성(correctness)를 보이는데 도움이 될 유용한 특성을 가져야한다.

-- 수학에서의 수학적귀납법과 유사 --

---

자 이제 이 특성들을 가지고 알고리즘의 정당성을 확인해보자
``
1. 초기조건 : 루프의 첫 반복(j=2)이 시작되기 이전에, $A[1, ... , j-1] == A[1]$ 이고 이 부분수열은 단일 원소로서 정렬되어 있다.

2. 유지조건 : for loop의 (2~8)줄에서 $A[j]$의 올바른 위치를 찾을 때 까지 $A[j-1], A[j-2], ... $을 오른쪽으로 한 칸씩 옮기는 작업을 한 뒤 $A[j]$ 값을 적절한 위치에 삽입한다.

그러면 부분 수열 $A'[1,...j]$ 는 기존 배열 $A[1,...j]$까지의 동일한 원소들을 정렬된 상태로 갖게 된다.
이 후, j가 1씩 증가하며 for loop의 다음 반복에서도 루프 불변성이 유지된다.

3. 종료조건 : while 문에서 $ j == A.length+1 $ 일 때 알고리즘은 종료한다. 앞에서 루프 불변성의 특징으로, 알고리즘이 종료 후 $A[1,...,A.length]$ 까지의 모든 원소를 포함하며 정렬된 상태를 유지하고 있음을 알 수 있다.

``
그러므로, 위 Insertion Sort Algorithm 은 정당하다.