삽입 정렬 (Insertion Sort)

들어가는 말

삽입 정렬은 배열의 앞부분을 정렬된 구간으로 유지하면서, 미정렬 구간의 첫 번째 값을 알맞은 위치에 삽입하는 방식으로 배열을 정렬한다.
값을 정렬된 구간의 적절한 위치에 끼워 넣기 때문에 삽입 정렬이라고 부른다.
시간 복잡도는 평균과 최악의 경우 O(n²)이지만, 이미 정렬된 배열에서는 O(n)으로 동작한다.

정렬 과정 살펴보기

6 3 8 2 5를 오름차순으로 정렬해 보자.

1회차

첫 번째 값 6만 있는 구간은 이미 정렬된 것으로 본다.
정렬되지 않은 구간의 첫 번째 값 3을 삽입할 값으로 기억한 뒤, 정렬된 구간의 마지막 원소부터 앞쪽으로 비교한다.
삽입할 값보다 큰 원소는 한 칸 뒤로 이동하고, 마지막으로 비어 있는 자리에 삽입할 값을 저장한다.

단계	비교	판단	삽입할 값	배열 상태
1회차 시작 전	-	두 번째 값 3을 삽입할 값으로 기억	3	6 3 8 2 5
1회차 1번째	6과 3	6이 더 크므로 뒤로 한 칸 이동	3	6 6 8 2 5
삽입	-	비어 있는 첫 번째 자리에 삽입	3	3 6 8 2 5

1회차가 끝나면 배열 앞부분의 3 6이 정렬된 구간이 된다.

2회차

3 6은 이미 정렬된 구간이므로 다음 값 8이 들어갈 위치를 찾는다.

단계	비교	판단	삽입할 값	배열 상태
2회차 시작 전	-	세 번째 값 8을 삽입할 값으로 기억	8	3 6 8 2 5
2회차 1번째	6과 8	6이 더 작으므로 이동하지 않음	8	3 6 8 2 5
삽입	-	원래 자리에 그대로 삽입	8	3 6 8 2 5

2회차가 끝나면 배열 앞부분의 3 6 8이 정렬된 구간이 된다.

3회차

3 6 8은 이미 정렬된 구간이므로 다음 값 2가 들어갈 위치를 찾는다.

단계	비교	판단	삽입할 값	배열 상태
3회차 시작 전	-	네 번째 값 2를 삽입할 값으로 기억	2	3 6 8 2 5
3회차 1번째	8과 2	8이 더 크므로 뒤로 한 칸 이동	2	3 6 8 8 5
3회차 2번째	6과 2	6이 더 크므로 뒤로 한 칸 이동	2	3 6 6 8 5
3회차 3번째	3과 2	3이 더 크므로 뒤로 한 칸 이동	2	3 3 6 8 5
삽입	-	비어 있는 첫 번째 자리에 삽입	2	2 3 6 8 5

3회차가 끝나면 배열 앞부분의 2 3 6 8이 정렬된 구간이 된다.

4회차

2 3 6 8은 이미 정렬된 구간이므로 다음 값 5가 들어갈 위치를 찾는다.

단계	비교	판단	삽입할 값	배열 상태
4회차 시작 전	-	다섯 번째 값 5를 삽입할 값으로 기억	5	2 3 6 8 5
4회차 1번째	8과 5	8이 더 크므로 뒤로 한 칸 이동	5	2 3 6 8 8
4회차 2번째	6과 5	6이 더 크므로 뒤로 한 칸 이동	5	2 3 6 6 8
4회차 3번째	3과 5	3이 더 작으므로 이동하지 않음	5	2 3 6 6 8
삽입	-	비어 있는 세 번째 자리에 삽입	5	2 3 5 6 8

첫 번째 원소는 1회차를 시작하기 전에 이미 정렬된 구간으로 보기 때문에 나머지 4개의 원소만 삽입하면 된다.
4회차가 끝나면 배열 전체가 정렬된 구간이 되므로 정렬이 끝난다.

회차별 정렬 과정 요약

회차	비교 횟수	이동 횟수	삽입할 값	정렬된 구간	배열 상태
시작 전	-	-	-	6	6 3 8 2 5
1회차	1번	1번	3	3 6	3 6 8 2 5
2회차	1번	0번	8	3 6 8	3 6 8 2 5
3회차	3번	3번	2	2 3 6 8	2 3 6 8 5
4회차	3번	2번	5	2 3 5 6 8	2 3 5 6 8

비교 횟수와 이동 횟수

원소가 n개인 배열을 오름차순으로 정렬한다고 가정하자.
배열이 이미 오름차순으로 정렬되어 있다면 삽입할 값은 바로 앞의 원소보다 크거나 같다.
따라서 각 회차에서는 바로 앞의 원소와 한 번만 비교하고, 원소를 이동하지 않은 채 다음 회차로 넘어간다.
원소가 5개라면 첫 번째 원소를 제외한 나머지 4개의 원소를 대상으로 4회차를 진행한다.
각 회차에서 한 번씩 비교하므로 비교 횟수는 1 + 1 + 1 + 1 = 4번이며, 이는 원소 개수보다 하나 작은 5 - 1번이다.
같은 방식으로 원소가 n개라면 n - 1회차를 진행하므로 모든 회차의 비교 횟수를 합하면 n - 1번이다.
비교 횟수가 원소의 개수에 비례하므로 시간 복잡도는 O(n)이다.
삽입할 값보다 큰 원소가 없으므로 뒤로 이동하는 횟수는 0번이다.

반대로 내림차순으로 정렬된 배열을 오름차순으로 정렬하려면 삽입할 값을 정렬된 구간의 모든 원소와 비교해야 한다.
삽입할 값이 정렬된 구간의 모든 원소보다 작으므로, 비교한 원소를 모두 뒤로 한 칸씩 이동해야 한다.
1회차에서는 1번, 2회차에서는 2번, 마지막 회차에서는 n - 1번 비교하므로 전체 비교 횟수는 1 + 2 + ... + (n - 1) = n(n - 1) / 2번이다.
비교한 원소마다 한 번씩 이동하므로 전체 이동 횟수도 n(n - 1) / 2번이다.
따라서 시간 복잡도는 O(n²)이다.

소스 코드

#include <stdio.h>

int main(void)
{
    int arr[] = { 6, 3, 8, 2, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);

    for (int i = 1; i < size; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]); // Result: 2 3 5 6 8

    return 0;
}

구현 설명

삽입 정렬은 첫 번째 원소만 있는 구간이 이미 정렬되어 있다고 가정하므로, 바깥 반복문의 변수 i는 1부터 시작한다.
각 회차에서 i는 정렬된 구간에 새로 삽입할 값의 위치를 의미한다.

key는 정렬된 구간에 삽입할 값을 저장한다.
값을 이동하는 과정에서 arr[i]가 덮어써질 수 있으므로, 반복을 시작하기 전에 삽입할 값을 key에 따로 저장해야 한다.

j는 정렬된 구간의 마지막 위치인 i - 1부터 시작한다.
arr[j]가 key보다 크면 arr[j]를 한 칸 뒤인 arr[j + 1]로 이동하고, j를 1만큼 줄여 앞의 값을 계속 확인한다.

while 반복문이 끝나면 j는 key 이하인 값의 위치를 가리킨다.
정렬된 구간의 모든 값이 key보다 크면 0번 인덱스까지 확인한 뒤 j는 -1이 된다.
두 경우 모두 j + 1이 key가 들어갈 위치이므로, 그 자리에 key를 저장한다.