삽입정렬

• sorted된 배열에 원소를 추가할때 sorted가 깨지지 않게 원소의 위치를 찾아서 넣는 알고리즘이 insertion sort다.
• 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다.
• 들어갈 위치를 선택하는데 N번, 선택하는 횟수로 N번이지만 선택정렬보다 약간 빠르다.
• 선택정렬과 똑같이 O(N^2) 의 시간 복잡도를 가진다.

삽입정렬의 작업 순서

• 가장 앞 인덱스의 원소가 정렬되어있다고 가정했을때
• 바로 뒷부분의 인덱스부터 올바른 위치로 insertion하는 알고리즘이다.
• temp변수를 두고 원소를 하나씩 swap하는 방법은 비용이 크다.
• 그래서 temp변수에 값을 넣고 기존 배열의 원소만 shifting한다음 만족하는 자리가 나오면 값을 넣는다.

원소의 인덱스만 shifting하는 pseudo code

template <typename Type>
void Insertion_Sort_without_Swap(Type *_array, int _n){
    for(int i = 1; i < _n; i++){
        Type temp = _array[i];
        for (int j=i; j<0; j--){
            if(_array[j-1] > tmp){
                _array[j] = _array[j-1];
            } else {
                _array[j] = tmp;
                break;
            }
        }
        if (_array[0] > tmp){
            _array[0] = tmp;
        }
    }
}

일반적인 삽입정렬의 형태

1. 두번째 노드부터 선택하여 이동한다.

2	4	3	1	9	6

이동하지 않는다.

2. 세번째 노드를 선택하여 이동한다.

2	4	3	1	9	6

2	3	4	1	9	6

3. 네번째 노드를 선택하여 이동한다.

2	3	4	1	9	6

2	3	1	4	9	6

2	1	3	4	9	6

1	2	3	4	9	6

4. 다섯번째 노드를 선택하여 이동한다.

1	2	3	4	9	6

이동하지 않는다.

5. 여섯번째 노드를 선택하여 이동한다.

1	2	3	4	9	6

1	2	3	4	6	9

정렬 완료.