나동빈님의 실전 알고리즘 강좌(Algorithm Programming Tutorial)를 바탕으로 학습한 내용을 정리한 포스트입니다.
실습 코드는 WebKit’s style guide를 따라 C언어로 작성되었습니다.
개인적으로 학습하며 작성한 포스트이기 때문에 오류가 있을 수 있습니다. 잘못된 내용이 있다면 댓글로 알려주세요.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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;
}

개요

삽입 정렬은 배열을 순회하면서 숫자를 가장 적절한 위치에 삽입하여 정렬을 수행하는 알고리즘입니다.
1, 10, 5, 8, 7, 6, 4, 3, 2, 9를 정렬하다보면 5가 삽입될 수 있는 위치가 _1_10_ 셋 중 하나입니다. 1 다음 10 이전이 가장 적절한 위치이기 때문에 해당 위치에 삽입하고 더 이상의 탐색은 하지 않습니다.

또한 어느정도 정렬이 되어있는 상태라면 삽입 정렬은 매우 빠른 속도로 정렬을 완료할 수 있다는 특징을 가지고 있습니다.

시간 복잡도

길이가 10인 배열을 정렬할 때 삽입 정렬을 사용하는 경우 10+9+8+...+1=55번 배열에 접근합니다.

이러한 등차수열은 N*(N+1)/2 즉, 10*(10+1)/2로 구하는 방법도 있는데, N이 매우 큰 숫자일 경우 +1과 /2는 의미가 큰 의미가 없기 때문에 일반적으로 N*N번 접근한다고 이야기합니다.

이를 Big-O 표기법으로 표기하면 O(N*N) => O(N²)이 됩니다.

삽입 정렬은 선택 정렬이나 버블 정렬과 달리 이미 탐색한 원소는 탐색하지 않기 때문에 비교적 속도가 빠르지만 최악의 경우는 동일합니다.

결론: 삽입 정렬의 시간 복잡도는 O(N²)이다.