Insertion Sort - 삽입 정렬과 코드

삽입 정렬은 정렬하려는 배열의 두 번째 원소부터 확인한다.

선택된 원소에서 앞과 비교해서 오름차순의 경우 앞의 원소가 더 크면 선택된 원소와 자리를 교환한다. 

 

위 그림에서 파란 화살표가 가리키는 게 Key라고해보자. 

두번째부터 시작해서 앞과 비교한다.

비교와 바꾸기가 끝나면 다음 반복에서 Key가 한칸 뒤로 옮겨진다.

 

이에 대해서 의사코드를 작성해보면 다음과 같다.

for ( i = 1 ; i < N; i++){
	key = arr[i];
    for ( j = i; j>0; j--){
    	if(key < arr[i-1]) arr[j] = arr[i-1]
        else break;
    }
    arr[j] = key
}

 

바깥 반복문은 2번째 원소부터 끝까지 돌고

안쪽 반복문은 바깥 반복문의 앞쪽을 돈다.

앞쪽을 돌다가 key값보다 작은게 나타나면 그 뒤에 key값을 삽입하는 코드라고 보면된다. 

 

 

배열이 만약 모두 정렬되어있다면,

키 값 바로 앞에서 확인하고 다음 키로 넘어가고, 넘어가고 해서 

O(N)시간 밖에 걸리지 않을 것이다. 

 

그래서 최선의 경우 시간복잡도는 O(N)이고 평균/최악은 O(N^2)이다. 

 

삽입 정렬을 C언어로 표현하면 아래와 같다. 

#include <stdio.h>
#include <string.h>

//오름차순 order 1, 내림차순 order -1
void insertion_sort(int n, int order, int arr[]){
    int i, j;
    for (i = 1; i < n; i++) { 
        int key = arr[i];
        for (j = i; j > 0; j--) { 
            if (order * key < order * arr[j-1]){
                arr[j] = arr[j - 1];
            }
            else break;
        }
        arr[j] = key;
    }
}

int main(void)
{
    int i;
    const int N = 5;
    int arr[N];
    for(i = 0; i < N; ++i){
        scanf("%d", arr + i);
    }
    insertion_sort(N, 1, arr);

    for(i = 0; i < N; ++i){
        printf("%d ", arr[i]);
    }
}