삽입 정렬 - Insertion Sort

오름차순으로 정렬하는 것을 기본으로 한다.

---

그림

삽입 정렬은 인덱스에서 하나를 잡아서, 올바른 곳에 삽입하는 그림을 가지고 있다.

보통 오름차순 정렬을 하기 때문에 왼쪽부터 순차적으로 인덱스를 하나씩 잡아서 작업을 하게 된다.

선택한 인덱스의 왼쪽에 정렬된 배열과 비교하여 정렬을 한다.

이 알고리즘의 그림은 이 정도만 기억하면 될 것 같고 예시를 보면서 구체적으로 살펴보자.

---

예시

3 4 1 2 7

5개의 정렬되지 않은 숫자들이 있다.

위에서 설명했다시피 인덱스 하나를 왼쪽부터 잡아서 올바르게 삽입하면 된다.

첫 번째 위치에 있는 '3'은 해봤자 왼쪽에 아무 배열이 없으므로 두 번째 위치부터 작업한다.

1) 3 4 1 2 7

왼쪽 배열과 비교했을 때 변경할 것이 없으므로 그대로 유지한다.

2) 3 4 1 2 7

왼쪽 배열과 비교해서 오름차순 정렬을 한다.

(변경 후)

1 3 4 2 7

3) 1 3 4 2 7

위와 동일한 작업을 한다.

(변경 후)

1 2 3 4 7

4) 1 2 3 4 7

이미 정렬되어 있으므로 작업을 종료한다.

---

코드