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

Insertion Sort

Insertion sort란 필요한 경우에만 위치를 바꿔 적절한 위치에 원소를 삽입하여 정렬하는 알고리즘입니다. 

그런데 이 필요한 경우를 알아내기 위해서는 조건이 필요합니다. 위치를 바꿀 요소의 앞 쪽 요소들이 모두 정렬되어있어야 하는 조건인데요.

그림을 통해 확인하면 다음과 같습니다.

 

4

3

5

1

2

 

4

3

5

1

2

 

3

4

5

1

2

 

3

4

5

1

2

 

1

3

4

5

2

 

1

2

3

4

5

1. 처음 위치해있는 4부터 확인합니다. 앞 쪽 요소가 없으니 건너뜁니다.

2. 다음 수 3을 확인합니다. 그 앞 요소인 4와 비교해 3보다 크니 위치를 바꿉니다.

3. 5를 확인합니다. 이미 1,2 과정에서 정렬이 되어있으므로 4하고만 비교를 합니다. 5가 더 크니 위치를 바꾸지않습니다.

4. 1을 확인합니다. 5부터 비교하여 5, 4, 3 순으로 크기를 비교하였더니 1이 제일 앞 요소까지 왔습니다. 따라서 1을 제일 앞에 위치시킵니다.

5. 마지막으로 2를 확인합니다. 정렬된 앞 쪽요소들과 비교해보니 5, 4, 3보다는 작고 1보다는 큽니다. 따라서 그 사이에 위치 시킵니다.

 

위 과정을 지나 오름차순으로 정렬되었습니다. 만약 수들이 내림차순으로 정렬되어있는 최악의 경우는 몇번의 비교 연산을 할까요?

0번부터 1번 2번 ... N-1번까지 공차가 1인 등차수열의 형태로 총 n(n+1)/2 번 연산을 합니다. 따라서 O(n^2)의 시간 복잡도를 가지게 됩니다. 선택정렬, 버블정렬과 마찬가지로 O(n^2)의 시간복잡도를 가지지만 실제 거의 정렬이 되어있는 배열의 경우는 시간복잡도가 훨씬 낮아져 배열이 거의 정렬되어있는 경우에 사용할 수 있다고 하네요.

 

 

다음은 파이썬 코드입니다.

 

import sys

def insertion_sort(list):
    for i,v in enumerate(list):
        while i-1 >= 0 and list[i-1] >= list[i]:
            list[i],list[i-1] = list[i-1],list[i]
            i -= 1
    return list

if __name__ == "__main__":
    numbers = list(map(int, sys.stdin.readline().split()))
    print(insertion_sort(numbers))

입출력