삽입 정렬은 뭐야?

개념

삽입 정렬은 다른 정렬 방식과는 다르게 정렬된 배열 A[1..n]에 정렬할 원소를 삽입할 인덱스를 계산하여 삽입하는 정렬 알고리즘입니다.

구현 방법

오름차순 정렬을 기준으로 살펴본 삽입 정렬의 구현 방법은 다음과 같습니다.

1. 배열을 순환하며 정렬할 원소 new_item을 선택한다.
2. new_item을 제외한 배열을 순환한다.
3. new_item보다 큰 원소를 찾게되면 해당 원소와 new_item의 위치를 교환한다.

파이썬 구현 코드

def insertion_sort(array):
    for i in range(1, len(array)):  # 1.
        prev = i - 1
        new_item = array[i]
        while prev >= 0 and new_item < array[prev]:  # 2.
            array[prev + 1] = array[prev]
            prev -= 1
        array[prev + 1] = new_item  # 3.
    return array

1. 첫번째 원소는 정렬되었다고 가정하기 때문에 두 번째 원소부터 순환을 시작한다.
2. 순환 중인 원소의 인덱스가 0보다 크거나 작고, new_item보다 작을 경우 new_item이 삽입될 인덱스를 계산한다.
3. new_item을 적잘한 위치(prev+1)에 저장한다.

그림으로 보는 삽입 정렬

삽입 정렬 정렬 과정

위의 그림은 삽입 정렬이 정렬되는 과정을 그림으로 그린 것입니다. 빨간색 글자는 정렬된 배열, 파란색 글자는 선택된 원소 new_item입니다.

시간 복잡도

삽입 정렬의 시간 복잡도는 평균, 최악의 경우 O(n^2)입니다. 원소의 개수가 n개인 배열이 있다고 가정하였을 때 1️⃣의 경우 n-1번을 순환합니다. 1️⃣을 순환할 때마다 2️⃣의 while문은 A[i]에 대해 최대 i-1번 순환을 하게 됩니다. 따라서 최악의 경우 수행 시간은 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2, 즉 O(n^2)가 됩니다.

 

하지만 최선의 경우, 거의 정렬되어 있는 경우에는 1️⃣을 n-1번 순환하고, 2️⃣는 순환을 하지 않기 때문에 O(n)의 시간이 들게 됩니다.

 

다음은 최선, 최악, 평균 경우의 2️⃣을 연산하는 횟수를 나타낸 것입니다. 

origin list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
best case comparison count: 0

origin list: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
result list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
worst case comparison count: 55

origin list: [7, 4, 9, 6, 3, 10, 0, 5, 2, 8, 1]
result list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
average case comparison count: 35

결론

버블 정렬과 선택 정렬은 k+1번째 원소를 정렬을 하기 위해 정렬되지 않은 원소를 모두 탐색해야 하지만 삽입 정렬의 경우 정렬된 배열에 삽입할 원소의 인덱스를 계산한다는 점에서 차이가 있습니다.

 

다른 정렬 알고리즘에서도 O(n)의 시간보다 빠른 정렬 알고리즘은 없기 때문에 정렬 기능을 구현해야 하는 상황에 놓이게 된다면 한 번쯤 고려해보는 것이 좋을 것 같습니다.

 

[참고 자료 및 깃허브 코드]

쉽게 배우는 알고리즘, 문병로, 한빛아카데미, 2018-01-20

깃허브(Github) - 삽입 정렬 알고리즘 구현