정렬 알고리즘 : 삽입 정렬 (Python)

삽입 정렬

---

삽입 정렬 gif

 

 

개념

 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다. 즉 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 삽입 정렬은 두 번째 데이터부터 시작한다. (첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.)

두 번째 요소 1부터 정렬을 시작한다.

 두 번째 요소 1은 3의 왼쪽이나 오른쪽으로 들어가는 2가지 경우가 있다. 오름차순이므로 3의 왼쪽에 1을 삽입합한다.

 

두 번째 요소까지 정렬된 모습

세 번째 요소를 정렬하려는 모습

 2는 1의 왼쪽, 1과 3의 사이, 3의 오른쪽에 들어갈 수 있다. 2의 바로 왼쪽에 있는 3과 비교했을 때 작으므로 왼쪽으로 이동하고, 1보다 크기 때문에 이동을 멈추고 삽입된다. 즉, 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때 까지 반복한다.

 

세 번째 요소까지 정렬한 모습

 이런 식으로 마지막 요소 4까지 적절한 위치를 찾아 삽입한다.

소스 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)): # 두번째 원소부터 마지막 원소까지 순
    for j in range(i, 0, -1): # i부터 1까지 감소 (현재 원소를 기준으로 왼쪽 원소들과 비교)
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
print('result', array)

 

시간 복잡도

O(N^2)

 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 단, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 그래서 최선의 경우 O(N)의 시간 복잡도를 가진다. 보통 퀵 정렬보다 비효율적이지만 정렬이 거의 되어 있는 상태에서는 퀵 정렬 알고리즘보다 강력하다. 

 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾼다. 하지만 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이라고 한다.