삽입 정렬 (Insertion Sort)

삽입 정렬은 값을 하나씩 꺼내서, 이미 정렬된 앞부분의 알맞은 자리에 끼워 넣는 정렬입니다.

한눈에 보기

• 손에 든 카드를 정렬하는 방법과 비슷합니다. 새 카드를 한 장 받으면 이미 정리된 카드들 사이에서 들어갈 자리를 찾아 끼워 넣습니다.
• 선택 정렬과 비슷하지만 좀 더 효율적인 정렬 알고리즘입니다.
• 2번째 원소부터 시작해서 그 앞(왼쪽) 원소들과 비교해 삽입할 위치를 정한 뒤, 원소들을 한 칸씩 뒤로 옮기고 그 자리에 값을 삽입합니다.
• 최선의 경우 O(n)이라는 매우 빠른 성능을 내서, 다른 정렬 알고리즘의 일부로 쓰일 만큼 좋은 알고리즘입니다. (예: Python의 sorted()가 쓰는 Timsort는 작은 구간을 (이진) 삽입 정렬로 처리합니다.)
• 분류로 보면 비교 정렬, 안정 정렬, 제자리 정렬입니다.

동작 과정

오름차순 정렬 기준입니다.

1. 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp를 그 앞에 있는 원소들과 비교하며, 들어갈 자리에 삽입합니다.
3. 1번으로 돌아가 다음 위치의 값을 temp에 저장하고 반복합니다.

예시 배열 [4, 2, 5, 1]로 따라가 보겠습니다. 표에서 | 왼쪽은 이미 정렬된 부분입니다.

단계	temp	배열 상태	설명
시작	-	[4 | 2, 5, 1]	첫 원소 하나는 이미 정렬된 것으로 봄
1	2	[2, 4 | 5, 1]	4가 2보다 커서 한 칸 뒤로 밀고, 맨 앞에 2 삽입
2	5	[2, 4, 5 | 1]	4가 5보다 작으니 비교 한 번으로 끝. 그 자리 그대로
3	1	[1, 2, 4, 5]	5, 4, 2를 차례로 한 칸씩 밀고, 맨 앞에 1 삽입

그림으로 보기

그림 출처: GimunLee/tech-refrigerator (Apache-2.0)

Python 코드

def insertion_sort(arr):
    """앞쪽 정렬된 부분에 값을 하나씩 끼워 넣는 삽입 정렬 (오름차순)"""
    for index in range(1, len(arr)):            # 1.
        temp = arr[index]
        prev = index - 1
        while prev >= 0 and arr[prev] > temp:   # 2.
            arr[prev + 1] = arr[prev]
            prev -= 1
        arr[prev + 1] = temp                    # 3.
    return arr


print(insertion_sort([4, 2, 5, 1]))
# 출력: [1, 2, 4, 5]

1. 첫 번째 원소 앞(왼쪽)에는 아무 원소도 없으므로 두 번째 위치(index = 1)부터 시작합니다. temp에 지금 위치의 값을 임시로 저장하고, prev에는 바로 앞 위치를 저장합니다.
2. prev가 음수가 아니고, 앞 위치의 값이 temp보다 크다면 그 값을 한 칸 뒤로 밀고(arr[prev + 1] = arr[prev]) prev를 한 칸 더 앞으로 옮깁니다. 두 값을 맞바꾸는 것이 아니라 뒤로 밀기만 하고, temp는 마지막에 한 번만 넣습니다.
3. 2번 반복문이 끝나면 prev는 temp 이하인 값 중 가장 오른쪽 위치를 가리킵니다. (그런 값이 없으면 -1) 그래서 바로 뒤인 prev + 1에 temp를 넣습니다.

시간복잡도와 공간복잡도

• 최악의 경우(거꾸로 정렬된 배열)에는 선택 정렬처럼 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2번 비교하므로 O(n²) 입니다.
• 하지만 이미 모두 정렬된 경우(최선)에는 각 원소가 앞 원소와 한 번씩만 비교하고 끝나므로 O(n) 입니다.
• 이미 정렬된 배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 됩니다. 자리를 찾는 탐색 말고는 추가 작업(오버헤드)이 매우 적기 때문입니다.

경우	시간복잡도
최선 (이미 정렬됨)	O(n)
평균	O(n²)
최악 (거꾸로 정렬됨)	O(n²)
공간	추가 메모리 O(1) (입력 포함 O(n))

• 공간: 주어진 배열 안에서 값을 밀고 넣기만 하므로 입력 배열 외에 temp, prev 정도인 O(1)만 더 씁니다.
• O 표기법이 낯설다면 시간 복잡도 글을 먼저 보면 좋습니다.

장점과 단점

장점

• 알고리즘이 단순합니다.
• 대부분의 원소가 이미 정렬되어 있으면 매우 효율적입니다.
• 정렬할 배열 안에서 값을 옮기는 방식이라 다른 메모리 공간이 필요 없습니다. → 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 입니다. 앞 값이 temp보다 클 때만 밀기 때문에 같은 값은 순서가 바뀌지 않습니다.
• 선택 정렬이나 거품 정렬 같은 다른 O(n²) 알고리즘보다 상대적으로 빠릅니다.

단점

• 평균과 최악의 시간복잡도가 O(n²)이라 비효율적입니다.
• 거품 정렬, 선택 정렬과 마찬가지로 배열이 길어질수록 비효율적입니다.

선택 정렬과의 차이

선택 정렬과 삽입 정렬은 k번째 반복이 끝나면 앞쪽 k개 원소가 정렬된 상태라는 점이 비슷합니다. 차이는 다음과 같습니다.

구분	선택 정렬	삽입 정렬
앞쪽 k개의 의미	전체에서 가장 작은 k개 (최종 위치 확정)	원래 앞쪽에 있던 k개를 정렬한 것 (나중에 더 밀릴 수 있음)
다음 원소를 위해 보는 범위	남은 원소 전부 탐색	자리를 찾을 때까지 필요한 만큼만 탐색
최선의 경우	O(n²)	O(n)

그래서 삽입 정렬이 훨씬 효율적으로 동작합니다.

정리

개념	비전공자 버전 요약
삽입 정렬	카드 한 장씩 꺼내 이미 정리된 손패 사이에 끼워 넣기
뒤로 밀기	새 값보다 큰 값들을 한 칸씩 뒤로 비켜 주기
최선 O(n)	거의 정렬된 자료라면 금방 끝남
선택 정렬과의 차이	선택은 남은 것 전부 확인, 삽입은 필요한 만큼만 확인

출처: GimunLee/tech-refrigerator (Apache-2.0), 코드는 Python으로 다시 작성

참고: gmlwjd9405 - 삽입 정렬(insertion sort)이란