[알고리즘]삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)이란?

자료의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입하여 정렬한다.

매 순서마다 해당 원소를 삽입해야할 위치를 찾아 해당 위치에 넣는다.

 

장점

• 레코드의 수가 적을 경우 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

• 레코드가 많고 크기가 크면 효율적이지 않다.

 

알고리즘의 순서

1. 이전 레코드보다 작은 레코드를 선택한다.
2. 한단계 씩 레코드를 교환하며 해당 레코드 위치를 찾아 넣는다.

삽입 정렬

---

의사 코드

전체적인 의사코드는 다음과 같다.

for( i = 0 to n){
    for( j = i -1 to 0, 현재 레코드가 키 레코드 보다 큰 경우){
        	현재 레코드를 다음 레코드에 삽입한다;
    }
    삽입해야 할 위치에 키 레코드를 삽입한다;
}

 

알고리즘 구현

void insertionSort(vector<int>& record){
    int N = record.size();
    int j, key;

    for(int i = 0; i<N; i++){
        key = record[i]; //키값 선정

        for(j = i -1; j >= 0 && record[j] > key; j--){
            record[j + 1] = record[j];  //한칸씩 밀기
        }
        record[j + 1] = key; //적절한 위치에 삽입
    }
}

시간 복잡도

2개의 반복 횟수

• 외부 반복문(N)
• 내부 반복문(N - 1)

 

T(n) = 1 + 2 + … + (n-2) + (n-1) = n(n-1)/2 = O(n^2)

 

---