[정렬] 삽입 정렬

작성일 | In

작동 과정

버블정렬은 인접한 원소를 비교/교체 하고,
선택정렬은 가장 작은 값을 선택해서 앞으로 넣어주면서 정렬을 했습니다.
삽입정렬은 모든 자료를 앞에서 부터 차례대로 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식으로 정렬을 진행합니다.

적절한 위치란, 현재 위치보다 앞 쪽에 있으면서 집어넣으면 정렬된 상태가 깨지지 않는 위치를 의미합니다.
31 25 12 22 11 을 정렬하자면,

1
2
3
4
5
"31" 25 12 22 11    첫번째 원소인 31을 적절한 위치에 넣는다.
31 "25" 12 22 11    두번째 원소인 25를 적절한 위치에 넣는다.
25 31 "12" 22 11    세번째 원소인 12를 적절한 위치에 넣는다.
12 25 31 "22" 11    네번째 원소인 22를 적절한 위치에 넣는다.
12 22 25 31 "11"    다섯번째 원소 11을 적절한 위치에 넣는다.

11 12 22 25 31 이렇게 정렬이 완료되었습니다.

구현

1
2
3
4
5
6
7
8
9
for(int i=0; i<n-1; i++){
    int key = arr[i+1];
    int j;
    for(j=i; j>=0; j--){
        if(arr[j] > key) arr[j+1] = arr[j];
        else break;
    }
    arr[j+1] = key;
}

이렇게 구현할 수 있습니다.

key에는 현재 위치의 다음 원소를 저장합니다.
for문을 돌리면서 현재위치부터 0까지 순회하면서 적당한 위치를 찾아 j에 저장합니다.
arr[j+1] = key;를 사용해서 key를 적적한 위치에 삽입합니다.

시간 복잡도 분석

먼저, 최선의 경우를 생각해봅시다.
최선의 경우는 이미 정렬이 되어 있는 경우입니다.
그런 경우에는 두 번째 for문이 돌지 않습니다. 그러므로 최선의 경우에는 O(n)입니다.

최악의 경우는 거꾸로 정렬된 상태입니다.
그런 경우에는 두 번째 for문이 처음에는 0번, 그 다음에는 1번, 그 다음에는 2번 … 돌게 됩니다.
모두 더하면 n*(n-1)/2 = (n2 - n) / 2 ∈ O(n2) 입니다.