정렬 (Sorting) (2) - 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort) 는 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘이다. 따라서 삽입 정렬 또한 선택 정렬과 마찬가지로 직관적으로 동작원리를 이해하기 쉬운 알고리즘이라고 할 수 있다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 다소 높은 편이지만 실행시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 또한 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬 되었을 때' 사용하면 그 효율은 배가 된다. 

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 아래와 같은 데이터를 삽입 정렬을 통해서 정렬하는 모습을 보자.

7 5 9 0 3 1 6 2 4 8

삽입 정렬은 두 번째 데이터부터 접근한다. 그 이유는 앞서 말했듯이 앞까지의 데이터는 이미 정렬되어 있다고 가정하기 때문이다. 두 번째 데이터인 5가 삽입될 위치를 찾으면 바로 첫 번째 데이터(7)의 앞에 삽입되어야 한다. 

5 7 9 0 3 1 6 2 4 8

그 다음 세 번째 데이터인 9에 접근해서 9가 들어갈 위치를 찾는다. 9는 앞의 5와 7보다 크므로 7의 오른쪽에 삽입 (그대로 유지) 해야 한다.

5 7 9 0 3 1 6 2 4 8

다음 네 번째 데이터인 0에 접근한다. 0은 5, 7, 9 보다 작으므로 5의 왼쪽에 삽입되어야 한다.

0 5 7 9 3 1 6 2 4 8

이러한 과정들을 모두 거치면 비로소 오름차순 정렬을 삽입 정렬로 완성한 형태를 얻을 수 있는 것이다.

0 1 2 3 4 5 6 7 8 9

---

소스코드는 위와 같다. 먼저 데이터의 개수 만큼 반복문을 돌린다. 첫 번째 반복문 내에서 두 번째 반복문을 돌리는데 이 때 해당 데이터의 인덱스부터 첫 번째 요소까지 접근한다. 두 번째 반복문 내에서는 앞선 요소보다 해당 요소가 작다면 계속 데이터의 위치를 바꿔주는 연산을 실시함으로써 삽입 정렬을 구현할 수 있는 것이다.

---

삽입 정렬의 시간 복잡도는 다음과 같다. 소스코드를 살펴보면 반복문이 2중으로 중첩되어 사용되었기 때문에 빅오 표기법을 사용해서 O(N^2) 이다. 그러나 삽입 정렬은 선택 정렬과는 다르게 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 수행해야 할 연산횟수가 급격하게 감소하기 때문에 그러한 경우에는 매우 효과적으로 동작한다. 최선의 경우에는 O(N) 으로 시간 복잡도가 개선됨을 알 수 있다.