[Python] 삽입정렬

삽입정렬

데이터의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

삽입정렬과정

예를 들어 [2, 4, 5, 1, 3] 이 있을 때, 자신의 위치를 찾아 그 위치에 들어간다.

[2, 4, 5, 1, 3] # 시작

[2 | 4, 5, 1, 3] # 2는 맨 앞에 위치하기 때문에 바꾸지 않는다.

[2  4 | 5, 1, 3] # 4부터 비교, 2의 뒤이므로 바뀌지 않는다.

[2  4  5 | 1, 3] # 5비교, 4의 뒤이므로 바뀌지 않는다.

[2  4 | 5, 1, 3] # 1비교, 1의 자리는 맨 앞이므로 한 칸씩 옮겨가며 1의 자리에 1을 넣는다.

[1  2  4  5 | 3] # 3비교, 3의 자리는 4와 5의 앞이므로 한 칸씩 옮겨가며 3의 자리에 3을 넣는다.

결과 [1, 2, 3, 4, 5]

 

삽입정렬 알고리즘

def ins_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        j = i - 1

        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
        

d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)

참고

삽입 정렬의 시간 복잡도는 O(N^2)이다.

하지만 [1, 2, 3, 4, 5] 같은 정렬이 완료된 특별한 경우에는 O(N)으로 정렬을 마칠 수 있다.