[Sorting Algorithms] Insertion Sort (삽입 정렬)

---

<모든 포스팅은 오름차순에 기반합니다.>

이론에만 몰두하다보면 항상 겪는 문제가 있다.

바로 머리로는 되는데 실제 구현에서 '어.. 이거 어떻게 해야되지..?'라고 멘붕에 빠지는 경우가 가끔 있다.

나에겐 Insertion Sort가 그랬다.

이론적으로 Insertion Sort는 Target Index인 나를 적절한 위치에 삽입하는 것이다.

그 적절한 위치는 왼쪽 Index가 모두 나보다 작은 위치이다.

오른쪽 Index를 고려하지 않는 이유는, 
- 오른쪽은 정렬되기 전의 Index들이며 
- 정렬하는 동안 순차적으로 나와 왼쪽 Index들만 비교할 것이기 때문이다.

나의 위치는 0번째 index부터 시작해 1회전을 끝낼때마다 1씩 증가한다.

[0]	[1]	[2]	[3]	[4]	[5]	[6]
5	3	1	7	11	9	4

3 < 5 이므로 자리를 교환한다.

3

5

1

7

11

9

4

----------------------------------------- 1회전 끝 ------------------------------------------

여기서 주의할 점은, 설명에선 교환이라고 했지만 실제로는 한번의 교환 으로 이루어지지 않는다는 점이다.

이는 2회전을 보면 명확히 알 수 있다.

[0]	[1]	[2]	[3]	[4]	[5]	[6]
3	5	1	7	11	9	4

Insertion Sort에서는 나와 내 앞의 모든 Index를 비교하게 된다.

3

1

5

7

11

9

4

Target Index인 나는 5보다 작기 때문에 교환된다.

1

3

5

7

11

9

4

그리고 이전 Index인 3보다도 작기 때문에 또 한 번 교환된다.

----------------------------------------- 2회전 끝 ------------------------------------------

1

3

5

7

9

11

4

이에 따라 마지막 회전에서 4는 앞선 모든 Index와 한번씩 교환되고 (즉, 뒤로 한칸씩 밀어내고)

3 < 4 이므로 3과 5 사이에 삽입되는 것이다.

이 과정은 버블 정렬 과 같다.

1

3

4

5

7

9

11

------------------------------------------ 정렬 끝 -------------------------------------------

실제 프로세스는 위처럼 반복적인 과정으로 동작하지만,

우리의 눈에는 3과 5 사이에 4가 자리를 찾아 삽입되는 것처럼 보이게 된다.

하지만 이렇게 개념만 정리하면 실제 구현에서 '앞의 Index를 한 칸씩 뒤로 밀어낸다.'라는 힌트를 떠올리기 어렵다.

그래서 Insertion Sort는 Linked List를 통해 설명하는 것이 가장 Fit하다고 생각한다.

<구현의 핵심>

- Target Index는 두 번째 원소부터 시작한다.

- Target Index 이전의 원소들은 모두 정렬된 상태다.

- Target Index 앞의 원소가 더 크면 서로 교환한다. (한 칸 밀어낸다.)

- 반복 하다가 Target Index보다 작은 원소를 만나면 멈춘다.