[파이썬 알고리즘] 삽입정렬(Insertion sort)이란?

삽입정렬

삽입정렬은 데이터 중 하나를 뽑아서(A) A 앞에 있는 데이터(B)와 비교해 $ A<B $이 되는 곳으로 A를 이동시키는 알고리즘입니다.

출처 : https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

로직

로직은 간단합니다. 하나 뽑고 데이터들과 비교합니다. 앞 데이터와만 비교하므로 두번째 인덱스부터 시작합니다.

예) data = [6,1,4,2]

• 1 뽑음 -> 앞 데이터 6보다 작음 -> [1,6,4,2]
• 4 뽑음 -> 앞 데이터 6보다는 작고 1보다 큼 -> [1,4,6,2]
• 2 뽑음 -> 앞데이터 4,6 보다 작고 1보다 큼 -> [1,2,4,6]

여기서 주의할 것은 계속 2번째 인덱스만 뽑지 않도록만 하면 됩니다. 계속해서 다음 인덱스로 넘어간다고 생각해야 합니다. 굉장히 중요합니다. 삽입정렬 알고리즘을 코드로 구현시 꼬이기 쉬운 부분입니다.
아무튼 순회횟수 +1 인덱스로 앞데이터와 하나씩 비교를 합니다.
버블 정렬에서는 뒤부터 정렬이 완성된 것에 반해 앞에서부터 하나씩 정렬이 됩니다.

 

데이터길이	비교	최대순회횟수
2	1	1
3	2	2
4	3	3

버블정렬과 같습니다. 다른 부분은 앞으로 정렬되므로 최대순회횟수를 변경하지 않아도 됩니다.

앞으로 비교할 예정이므로 정렬이 된 경우 정지하면 그만입니다.

코드작성

1. 순회 for문과 비교 for문을 만듭니다.
2. 순회(index1) 가 시작하면 앞 데이터와 비교할 for문 index2를 뽑습니다. index2은 index1 다음수부터 시작해야 하므로 range(index+1,0,-1)으로 되고 앞에 데이터와 하나씩 비교할 예정입니다. (data[index2]<data[index2-1])
3. data[index2]<data[index2-1] 이면 swapping
4. 그렇지 않다면 앞에는 정렬이 되어있는 것이므로 더이상 할게 없습니다. break

def insertion_sort(data):
    for index1 in range(len(data) - 1):
        for index2 in range(index1 + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2] #swapping
            else:
                break
    return data

실제로 적용해봅시다.

import random

data = random.sample(range(100), 50)
print (insertion_sort(data))

 

알고리즘 분석

시간복잡도는 다음과 같습니다.

시간복잡도

n개의 데이터일 경우 모두 이미 정렬이 되어있다면 n 번 순회만 돌면 됩니다. O(n) 입니다.

최악의 경우, n-1 루프를 돌면서 비교를 한번씩 다 해야합니다. 연산은 루프가 올라가면서 비교횟수도 올라가므로 다음과 같이 나옵니다.
$$ 1+2+...+(n-1) = \frac{(n-1)(n)}{2} $$

따라서 $ O(n^2) $ 이 됩니다.

 

 

함께보면 좋은 글

[파이썬 알고리즘] 버블 정렬(bubble sort)이란?