삽입정렬

• 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. 세번째 노드를 선택하여 이동한다.

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

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

이동하지 않는다.

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

정렬 완료.