| 삽입정렬 개념 | 삽입정렬 알고리즘 | 삽입정렬 분석 |

• 삽입정렬은 매우 간단한 정렬 방법으로 소량의 자료를 처리하는데 유용
• 파일을 구성하고 있는 부파일(subfile)의 레코드들이 이미 정렬이 되어 있다고 가정
• 한 번에 한 개의 새로운 레코드를 입력하여 정렬되어 있는 사이트의 적당한 위치를 찾아서 레코드를 삽입
• 따라서 새롭게 삽입된 레코드를 포함하여 파일은 항상 정렬된 상태를 유지

■ 삽입정렬 과정

  ① 두 번째 키를 기준으로 하여 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열
  ② 세 번째 키를 기준으로 하여 두 번째 키와 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열
  ③ 계속하여 n번째 키를 앞의 n-1개의 키와 비교하여 삽입될 적당한 위치를 찾아 삽입한다.

30 15 20 17 40 ------>  초기상태
30 15 20 17 40 ------>  15 이전의 수를 비교해서 15 < 30 이므로 삽입
15 30 20 17 40 ------>  20 이전 수만 비교. 20 < 30 이므로 삽입 
15 20 30 17 40 ------>  17 이전 수만 비교. 17 < 20 이므로 삽입
15 17 20 30 40 ------>  40 이전수 비교. 삽입은 없음
15 17 20 30 40 ------>  정렬완료