삽입 정렬 (Insertion Sort)

1. Introduction

삽입 정렬은 원소가 들어갈 자리를 찾고 그 위치에 삽입한 뒤, 그 보다 큰 원소를 뒤로 밀어내는 방식의 정렬 알고리즘이다. 선택 정렬과 같이 $O(n^2)$의 시간 복잡도를 가지고 있다.

2. Approach

다음 이미지는 삽입 정렬의 과정을 보여준다. 출처는 위키피디아.

Animation of Insertion Sort

Example of Insertion Sort

다음 코드는 파이썬에서 구현한 삽입 정렬이다.

def insertion(arr, a, b):
    for i in range(a+1, b+1):
        key = arr[i]
        j = 0
        
        for j in range(i-1, a-2, -1):
            if arr[j] > key:
                arr[j+1] = arr[j]
            else:
                break
        arr[j+1] = key

3. Discussion

삽입 정렬은 stable한 정렬에 속하며 in-place한 알고리즘에 속한다.

삽입 정렬은 리스트가 정렬될수록 효율이 증가하며, 특히 이미 정렬된 리스트를 정렬할 경우 시간복잡도가 $O(n)$으로 가장 빠르다. 이런 장점덕에 삽입정렬은 다른 정렬에 hybrid하게 쓰이기도 한다.