9삽입 정렬

 

◼︎ 9-1 삽입 정렬 과정

일반적인 삽입 정렬은 처리할 대상 범위에 있는 맨 앞 값을 적절한 위치에 넣는 과정을 반복합니다. 이 과정이 한 번 끝날 때마다 대상 범위에 있는 맨 앞의 값이 제 위치를 찾아 가므로 정렬 대상 범위는 하나씩 줄어듭니다.

이해를 돕기 위해 이미 정렬이 끝난 부분과 앞으로 처리될 대상 범위 사이에 세로선(|)을 넣어 구분하였습니다.

 

| 2 4 5 1 3 ← 시작

2 | 4 5 1 3 ← 맨 앞에 있는 2는 옮기지 않아도 됩니다.

2 | 4 5 1 3 ← 4의 위치를 맞춥니다. 2 바로 다음이므로 위치가 변하지 않습니다.

2 4 | 5 1 3 ← 대상 범위를 하나 줄입니다.

2 4 | 5 1 3 ← 5의 위치를 맞춥니다. 4 바로 다음이므로 이번에도 위치가 그대로입니다.

2 4 5 | 1 3 ← 대상 범위를 하나 줄입니다.

1 2 4 | 5 3 ← 1의 위치를 맞춥니다. 1은 2, 4, 5보다 작으므로 이 값들을 한 칸씩 오른쪽으로 옮긴 다음 비어 있는 공간에 1을 넣습니다.

1 2 4 5 | 3 ← 대상 범위를 하나 줄입니다.

1 2 3 4 | 5 ← 마지막으로 3의 위치를 맞춥니다. 3은 4, 5보다 작으므로 4와 5를 한 칸씩 오른쪽으로 옮긴 다음 비어 있는 공간에 3을 넣습니다.

1 2 3 4 5 | ← 대상 범위를 하나 줄입니다. 더는 자료가 없으므로 종료합니다(최종 결과).