All that Sort - [2] Insertion Sort (삽입정렬)

이번에 알고리즘 수업을 Self-Study 로 다시 듣게 된 김에 알고리즘 관련 포스팅을 다시 시작해볼까 한다. 

Bubble Sort는 사실 정렬이라고 부르기도 민방한 정렬이다. 

삽입정렬은 그보다는 조금 더 elegant 한 방법이라 할 수 있다.

우선 pseudocode 를 보자.

1  for i = 1 to n-1 do

2      tmp = a[i]

3      j = i

4      while j > 0 AND a[j-1] > tmp do

5           a[j] = a[j-1]

6            j = j - 1

7   a[j] = tmp

우선 0번 원소는 건너뛰고 1번부터 차근차근히 보면서 가는 것이다.

즉, 1번원소일 때는 0~1을 정렬하고, 2번원소일때는 0~2를 정렬하고.. 

이런 식으로 맨 뒤의 원소의 적절한 위치를 찾아서 마지막 원소까지 위치를 찾아주면 끝.

생각보다 간단하다. 

예제를 보면서 생각해보자.

그림에서 보이는 것처럼, 앞쪽부터 차례로 정렬되는 것을 볼 수 있다. 

결국 삽입정렬은 뒤의 원소들을 이미 정렬된 공간 안에 "삽입"하는 정렬이라 할 수 있다.

이 알고리즘의 복잡도는  O(n²) 인데, 최상의 케이스에선 O(n)까지도 가능하다. 또한 in-place이며 stable하고

비교적 구현이 쉽다는 특징이 있다.