[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬이란?

삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다. 필요할 때만 위치를 변경하므로 선택 정렬보다 더 효율적인 방식입니다. 키 순으로 정렬된 사람들이 일렬로 서 있는데, 다음 원소가 정렬된 사람들 사이를 비집고 들어가는 방식입니다.

 

선택 정렬 예

예) [4, 6, 2, 9, 1]

 

1단계 : [4, 6, 2, 9, 1]        #4 < 6 이므로 위치 변경을 하지 않습니다.

              [4, 6, 2, 9, 1] 

2단계 : [4, 6, 2, 9, 1]        #6 > 2 이므로 위치 변경, 4 > 2 이므로 위치 변경을 합니다. 

              [2, 4, 6, 9, 1]

3단계 : [2, 4, 6, 9, 1]        #6 < 9 이므로 위치 변경을 하지 않습니다. 

              [2, 4, 6, 9, 1]

4단계 : [2, 4, 6, 9, 1]        #2,4,6,9 > 1이므로 4번 위치 변경을 합니다.

              [1, 2, 4, 6, 9] 

 

삽입 정렬 python 코드

input = [4, 6, 2, 9, 1]

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

insertion_sort(input)
print(input)

print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))

 

삽입 정렬의 시간 복잡도

O(N^2) 만큼 걸립니다. 버블 정렬과 선택 정렬은 최선이든 최악이든 항상 O(N^2) 만큼의 시간이 걸리지만, 삽입 정렬은 최선의 경우에는 Ω(N) 만큼의 시간 복잡도가 걸립니다. 거의 정렬이 된 배열이 들어간다면 break 문에 의해서 더 많은 원소와 비교하지 않고 탈출할 수 있기 때문입니다.