1삽입 정렬로 줄 세우기

 

1 | 학생이 열 명 모인 운동장에 선생님이 등장합니다.

2 | 선생님은 열 명 중 제일 앞에 있던 승규에게 나와서 줄을 서라고 합니다. 승규가 나갔으니 이제 학생이 아홉 명 남았습니다.

3 | 이번에는 선생님이 준호에게 키를 맞춰 줄을 서라고 합니다. 준호는 이미 줄을 선 승규보다 자신이 키가 작은 것을 확인하고 승규 앞에 섭니다.

4 | 남은 여덟 명 중 이번에는 민성이가 뽑혀 줄을 섭니다. 민성이는 준호보다 크고 승규보다는 작습니다. 그래서 준호와 승규 사이에 공간을 만들어 줄을 섭니다(삽입).

5 | 마찬가지로 남은 학생을 한 명씩 뽑아 이미 줄을 선 학생 사이사이에 키를 맞춰 끼워 넣는 일을 반복합니다. 마지막 남은 학생까지 뽑아서 줄을 세우면 모든 학생이 제자리에 줄을 서게 됩니다.

 

그림 9-1 삽입 정렬