[Algorithm] Insertion Sort (삽입 정렬)

0. Insertion Sort (삽입 정렬) 이란?

 

Insertion Sort란, 앞에서부터 순서대로 보면서 앞에 있는 모든 원소가 정렬이 되어있다는 가정 하에 현재 원소의 위치를 적절하게 집어넣는 정렬이다. 앞의 모든 원소가 정렬이 되어있으므로, 현재 위치의 원소가 어디에 들어갈 지 앞의 모든 원소를 한 번만 돌아보면 알 수 있을것이다. 이 과정을 현재 원소가 두번째일때부터 n번째일때까지 반복한다.

 

n개의 원소에 대해 값 삽입을 수행해야 하는데, k번째 원소의 경우 최대 k-1개의 원소를 이동해야 하므로 비교 연산이 1+2+...+(n-1) = n*(n-1)/2번 일어난다. 따라서 시간복잡도는 O(n^2)이다.

 

1. 구현

n = int(input())
nums = input()
num = nums.split()
min = 101
min_idx = 0

for i in range(n):
    num[i] = (int)(num[i])

for i in range(1, n):
    j = i - 1
    key = num[i]
    while j >= 0 and num[j] > key:
        num[j+1] = num[j]
        j -= 1
    num[j+1] = key


for i in range(n):
    print(num[i], end=' ')

key는 삽입하고자 하는 i번째 원소를 의미한다. 따라서 j는 0부터 i-1까지 돌며 key가 삽입될 위치를 찾는다. 앞의 모든 원소가 정렬되었다는 가정이 있으므로 굳이 모든 원소를 비교하지 않고 뒤에서부터 앞으로 순회하며 비교하면 된다. key보다 작으면서 가장 큰 원소를 발견하면 while문은 종료되고, 종료되었을 때의 index값인 j의 바로 뒤에 key를 삽입한다. 

 

왜 swap으로 구현하지 않았냐면, key가 num[i]의 값을 보존하고 있으므로 앞으로 하나씩 땡긴 후에 보존된 값을 가운데에 넣어주면 손실되는 값 없이 구현할 수 있다.