[알고리즘] 삽입정렬(Insertion sort)이란?

1. 삽입정렬이란?

Insertion sort

삽입정렬(Insertion sort)이란, 단어 그대로 삽입(insertion)을 이용한 정렬이라고 할 수 있다. 정렬하고자 하는 대상인 키와 정렬된 키들의 목록이 주어지면, 키를 정렬 순서가 유지되도록 삽입하는 것을 말한다. 즉, 삽입 정렬이란 정렬하고자 하는 원소를 key로 설정한 뒤 그 앞의 정렬된 목록과 비교해가면서 어느 위치에 들어가게 될지를 결정하는 정렬을 말한다고 할 수 있다.

 

만약 사이즈가 n인 어레이가 주어지면, 삽입정렬에서는 두 번째 원소부터 정렬을 시작하게 된다. 두 번째 원소부터 시작하는 이유는 삽입 정렬을 하기 위해서는 정렬의 대상이 되는 key와 정렬이 들어갈 수 있는 정렬된 목록이 필요하기 때문인데, 첫 번째 원소를 key로 설정하게 되면 key가 들어갈 목록이 없기 때문이다.

 

삽입 정렬에서 기억해야 할 것은 key를 비교 대상이 되는 정렬된 목록의 알맞은 위치에 삽입하기 위해, key 앞의 원소들이 이미 정렬된 상태여야한다는 점이다.  

 

2. 삽입정렬의 예시

만약 array A = {5,2,4,6,1,3}일 때, 삽입정렬로 A를 오름차순 정렬을 한다고 가정해보자. 

왼쪽 : 설정된 키 / 오른쪽 : 정렬 결과

삽입정렬의 경우 두 번째 원소부터 정렬을 시작하므로 첫 번째로 선택된 key는 두 번째에 위치한 2가 된다. 이후 이 2는 앞의 원소인 5와 비교하게되고, 5와 비교했을 때 2는 5보다 작은 수이기 때문에 5가 한 칸 뒤로 오고 그 자리에 2가 위치하게 된다.

왼쪽 : 설정된 키 / 오른쪽 : 정렬 결과

두 번째 원소의 비교가 끝났으므로, 그 다음인 세 번째도 진행한다. 세 번째에 위치한 4가 key가 되고, 앞의 리스트인 [2,5]와 비교해서 2보다 크고 5보다 작으므로 그 사이에 들어가는 식으로 정렬이 진행된다. 

그렇게 두 번째 원소부터 마지막 원소까지 진행하게 되면 정렬이 완료된 array A를 얻을 수 있게 된다. 

 

3. 삽입정렬의 pseudo code

for j = 2 to A.length
	key = A[j]
    # insert A[j] into the sorted sequence A[1..j-1]
    i = j-1
    while i > 0 and A[i] > key
    		A[i+1] = A[i]
            i = i-1
    A[i+1] = key

두 번째 원소부터 시작해서 주어진 배열의 끝까지 진행하므로 j가 2부터 A의 길이까지로 설정된다.

while문의 조건은 i가 0보다 zm고, A[i]가 key보다 큰 경우이다. 이 조건이 참이면 A[i]는 key보다 큰 값이므로 A[i]를 A[i+1]에 복사해주고, i를 1 감소시켜 다음 원소와 비교하게 된다. 이 과정을 반복하다가 A[i]가 key보다 작아지거나 i가 0이 되는 경우 while문을 빠져나오게 된다.

while문에서 빠져나온다는 것은 key가 들어갈 위치를 찾았다는 뜻이므로 정렬의 대상인 key를 A[i+1]에 삽입하게 된다. 

 

4. 공간복잡도

삽입정렬의 경우 입력으로 주어진 배열 안에서 되도록 해결하는 in-place알고리즘이기 때문에 공간복잡도는 O(n)이다.

물론 배열의 크기(n) + key를 저장하는 공간(c)을 사용해서 key만큼의 저장 공간이 추가로 필요하긴 하지만, 복잡도를 표현하는 경우 낮은 차항의 경우 큰 영향을 주지 않기 때문에 O(n)으로 표현한다. 

 

5. 시간복잡도

• Best case
  • 이미 정렬이 된 경우, 이동하지 않고 앞의 숫자와 한 번씩만 비교 하게 되므로 이 경우 시간 복잡도는 O(n)이다.
• Worst case
  • 하지만 역 순으로 정렬이 된 경우, 매 번 모든 앞의 숫자와 비교함과 동시에 앞으로 옮겨가야 하므로 시간 복잡도는 O(n^2)이 되게 된다.