[Algorithm] 삽입 정렬(Insertion Sort) 이란?

삽입 정렬 (Insertion Sort)

삽입 정렬이란 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 알고리즘이다.

 

삽입 정렬의 특징은 다음과 같다.

 

• 두 번째 키와 첫 번째 키를 비교하여 순서대로 나열(1회전)하고, 이어서 세 번째 키를 1,2 번째 키와 비교하여 순서대로 나열(2회전)하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 알고리즘이다.
• 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다.

예제를 통해서 삽입 정렬을 이해해보자.

삽입 정렬 예제

• 초기 상태 : [8, 5, 6, 2, 4]

1회전

• 두 번째 레코드 5를 Key로 지정하여 이전 자료들과 비교한다.
• Key(5)가 첫 번째 레코드인 8 보다 작으므로, 8을 Key의 자리에 넣고 5를 첫 번째 자리에 넣는다.
• 1회전 후 정렬 상태 : [5, 8, 6, 2, 4]

2 회전

• 세 번째 레코드 6을 Key로 지정하여 이전 자료들과 비교한다.
• Key(6)가 두 번째 레코드인 8 보다 작으므로, 8을 세 번째 자리에 놓는다.
• 다음으로 Key(6)와 첫 번째 레코드인 5를 비교하면 Key 값이 더 크기 때문에 첫 번째 레코드의 이동 없이 Key를 두 번째 자리에 놓고 회전이 끝난다.
• 2회전 후 정렬 상태 : [5, 6, 8, 2, 4]

3 회전

• 네 번째 레코드 6을 Key로 지정하여 이전 자료들과 비교한다.
• Key(2)가 세 번째 레코드인 8 보다 작으므로, 8을 네 번째 자리에 놓는다.
• 다음으로 Key(2)가 두 번째 레코드인 6 보다 작으므로, 6을 세 번째 자리에 놓는다.
• 마지막으로 Key(2)가 첫 번째 레코드인 5 보다 작으므로, 5를 두 번째 자리에 위치시키고 Key를 첫 번째 레코드에 놓는다.
• 3회전 후 정렬 상태 : [2, 5, 6, 8, 4]

4 회전

• 다섯 번째 레코드 4를 Key로 지정하여 이전 자료들과 비교한다.
• Key(4)가 네 번째 레코드인 8 보다 작으므로, 8을 다섯 번째 자리에 놓는다.
• 다음으로 Key(4)가 세 번째 레코드인 6 보다 작으므로, 6을 네 번째 자리에 놓는다.
• 다음으로 Key(4)가 두 번째 레코드인 5 보다 작으므로, 5를 세 번째 자리에 놓는다.
• 마지막으로 Key(4)와 첫 번째 레코드인 2를 비교하면 Key 값이 더 크기 때문에 첫 번째 레코드의 이동 없이 Key를 두 번째 자리에 놓고 회전이 끝난다.
• 4회전 후 정렬 상태 : [2, 4, 5, 6, 8]

삽입 정렬 파이썬(Python) 코드

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

        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            i -= 1
        
        A[i+1] = key

        print("{} 회전 후 배열 상태 : {}".format(j, A))

A = [8, 5, 6, 2, 4]
insertion_sort(A)

코드 수행 결과는 다음과 같다.