삽입 정렬(Insertion sort)

정렬 알고리즘 중 하나인 삽입 정렬(Insertion sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다.

---

기본 개념

삽입 정렬은 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 같은 방식으로 작동합니다. 처음에는 손에 카드가 없는 상태로 시작합니다. 카드 더미에서 카드를 한 장씩 가져와서 왼손에 쥐는데, 새로 가져온 카드를 알맞은 위치에 넣습니다. 알맞은 위치를 찾기 위해서 새로 가져온 카드를 왼손에 쥔 카드와 비교합니다. 오른쪽부터 왼쪽으로 차례대로 비교합니다.

예시

a) 오른쪽으로 갈수록 큰 수가 오도록 정렬을 한다고 하겠습니다. 순서가 [5, 2, 4, 6, 1, 3]인 배열을 정렬하고자 합니다. 계속해서 카드에 비유하자면 우선 제일 왼쪽에 있는 카드 5를 왼손에 쥡니다. 새로운 카드 2를 뽑습니다. 5와 2를 비교합니다. 5가 2보다 크므로, 5를 오른쪽에 위치하도록 놓습니다.

b) 그 다음에는 카드 4를 알맞은 위치에 넣어야 합니다. 회색이 칠해진 부분은 정렬이 끝난 카드들입니다. 정렬이 끝난 카드 중에서 가장 큰 수인 5부터 비교합니다. 5가 4보다 크므로 카드 5의 위치를 한 칸 오른쪽으로 옮깁니다. 이번엔 4와 2를 비교합니다. 2는 4보다 크지 않으므로, 그대로 두고 카드 4는 5가 있던 위치에 둡니다.

c) 그 다음 카드 6을 5와 비교합니다. 5는 6보다 크지 않으므로, 그대로 두고 6의 위치도 그대로 둡니다.

d) 그 다음 카드 1을 6과 비교합니다. 6이 1보다 크므로 카드 6의 위치를 한 칸 오른쪽으로옮깁니다. 이번엔 1과 5를 비교합니다. 이런식으로 1보다 크지 않은 수가 나타날 때까지 비교하면서 위치를 이동시킵니다. 1보다 큰 수가 더 이상나타나지 않거나 마지막에 도착하면 비교를 멈춥니다.

e) 마지막으로 3과 6을 비교합니다. 6이 3보다 크므로 카드 6의 위치를 한 칸오른쪽으로옮깁니다. 이 과정을 반복하면 모든 수가 제자리를 찾습니다.

코드

삽입 정렬의 의사 코드는 다음과 같습니다.

여기서 key는 새로 뽑은 카드에 해당합니다. while에는 두 개의 조건이 있습니다. 모든 카드와 비교가 끝났거나, 이미 정렬된 수들 중에서 가장 큰 수가 key보다 크면 while 구문은 지속됩니다.

파이썬 코드는 다음과 같습니다.

def insertion_sort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i > -1 and A[i] > key:
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

 

삽입 정렬의 특징 중 하나는 in place로 동작한다는 점입니다. 즉 정렬된 새로운 배열을 반환하는 게 아니라, 정렬하고자 하는 배열 그 자체 내에서 정렬이 이루어져, 추가적으로 필요한 메모리가 거의 없습니다.

 

복잡도

삽입 정렬의 복잡도는 정렬하고자 하는 배열에 따라 다릅니다. 이미 정렬되어 있는 배열이라면, while 구문은 작동하지 않으므로 배열의 크기(n)만큼 시간이 걸립니다. 반대로 거꾸로 정렬이 되어 있다면 최악입니다. 이 경우에는 for가 돌 때마다 while 구문이 j번만큼 작동하며, j는 for 구문이 반복될 때마다 1씩 커집니다. 이를 계산하면 $\Theta(n^2)$만큼의 시간이 걸립니다.