삽입 정렬 [Python / 파이썬]

1. 삽입 정렬(Insertion Sort) 

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬(Insertion Sort)라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

 

선택 정렬

2022.01.06 - [CS/알고리즘,자료구조] - 선택 정렬 [Python / 파이썬]

선택 정렬 [Python / 파이썬]

 

 

출처 : 위키 백과

위와 같이 데이터가 있다고 가정해보자 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.

 

a) 첫 번째 데이터 3은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 7이 어떤 위치로 들어갈지 판단한다. 3의 왼쪽으로 들어가거나 혹은 오른쪽으로 들어가는 두 경우만 존재한다. 이경우 오름차순으로 정렬하고자 하므로 3의 오른쪽에 삽입한다.

 

b) 이어서 2가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 2는 3보다 작기 때문에 3의 앞에 삽입한다.

 

c) 이어서 5가 어떤 위치에 들어갈지 판단한다. 5는 3보다는 크고 7보다는 작기 때문에 3과 7 사이에 삽입한다.

 

d) 이어서 1이 어떤 위치에 들어갈지 판단한다. 1은 2, 3, 5, 7과 비교했을 때 가장 작기 때문에 첫 번째 위치에 삽입한다.

 

e) 이어서 4가 어떤 위치에 들어갈지 판단한다. 4는 3보다는 크고 5보다는 작기 때문에 3과 5 사이에 삽입한다.

 

이와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 f)와 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

삽입 정렬은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다. 그림 c)를 보면 회색으로 칠해진 수들은 오름차순으로 정렬되어있는 것을 알 수 있다. 이러한 특징 때문에 특정 한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

예를 들어 c)에서 5는 한 칸씩 왼쪽으로 이동하다가 자신보다 작은 3을 만났을 때 그 위치에 삽입된다. 다시 말해 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다. 

파이썬으로 작성한 소스코드는 다음과 같다.

 

def insert_sort(array):
	for i in range(1, len(array)):
		for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소
        	if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            	array[j], array[j - 1] = array[j - 1], array[j]
            else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            	break
	return array

 

---

2. 삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 여기서 꼭 기억할 내용은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 정렬해야 할 수가 한 번의 비교만 수행하면 되므로 O(N)의 시간 복잡도를 가진다.

비교 횟수를 C라고 했을 때,

삽입 정렬은 C_min 최선, C_max 최악의 경우 C_min = O(N), C_max = O(N^2)의 시간 복잡도를 가진다.