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

아래의 숫자들을 오름차순으로 정렬한다고 생각해보자

 

1  10  5  8  7  6  4  3  2  9

 

버블 정렬과 선택정렬을 사용 할 수도 있지만, 삽입 정렬을 사용하면 특정상황에 따라서는 보다 효율적으로 정렬할 수 있다.

 

다른 정렬들은 무조건 위치를 바꾸는 방식이였지만, 삽입정렬의 다른점은 '필요할 때만' 위치를 바꾼다는 것이다.

 

 

 

예를들어 보자,

아래와 같은 숫자들을 오름차순 정렬한다고 했을때, 삽입정렬은

 

1  10  5  8  7  6  4  3  2  9

 

 바로 옆의 10과 대소를 비교한다.

 

10은 1의 앞 혹은 지금 현재 자리에 있을 수 있는데, 오름차순이기때문에 현재 위치를 그대로 유지하면 된다.

 

그다음 10 과 5를 비교해보면,

5가 더 작기때문에 10과 5의 자리를 바꿔준다.

 

조금 더 쉽게 생각하면 빈칸이 있다고 생각을 해보면 된다.

 

1  _ 10 _  5  8  7  6  4  3  2  9

 

5가 들어갈수 있는 부분은 _ 칸으로 나타있는데 10보다 크다면 오른쪽 _ 에 위치하고 그렇지 않다면 오른쪽 _ 에 위치해야한다.

5는 10보다 작으므로, 왼쪽에 위치한다.

 

1  5 10 _  8  7  6  4  3  2  9

 

이러한 과정을 반복하고 나면,

 

1 2 3 4 5 6 7 8 9 10

 

이라는 결과를 얻게 된다.

 

버블정렬의 경우, 계속 해서 정렬을 해가며 오름차순 정렬이 될때 까지 반복하지만,

 

삽입정렬은 알맞은 인덱스 위치를 찾아들어간다.

 

 

따라서,

2 3 4 5 6 7 8 9 10 1

과 같이 정렬이 많이 되어있는 상태라면

 

비록 BigO는 O(N^2) 일지라도

 

삽입정렬은 필요할때만 값을 이동시켜주기 때문에 다른 정렬 알고리즘 보다 훨씬 효율적이다.

 

 

#include <stdio.h>

int main(void)
{
    int i,j,temp;
    int array[10] = {1,10,5,8,7,6,4,3,2,9};
    for(i = 0; i < 9; i++)
    {
        j=i;
        while(array[j] > array[j+1]){
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            j--;
        }
    }

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

    return 0;
}