■ 삽입 정렬 개념
• 삽입정렬은 매우 간단한 정렬 방법으로 소량의 자료를 처리하는데 유용
• 파일을 구성하고 있는 부파일(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 ------> 정렬완료
■ 삽입 정렬 알고리즘
procedure INSERT(R,n)
for j ← 2 to n do
R ← Rj
K ← Kj
i ← j-1
while i >0 and Ki >K do
Ri+1 ← Ri
i ← i-1
end
Ri+1 ← R
end
end INSERT
■ 성능
▷ 최적 - 입력 데이타가 정렬하고자 하는 순서대로 배열되어 있는 경우 최소 비교 횟수 : n-1 ▷ 최악 - 입력 데이타가 역순으로 정렬되어 있는 경우 최대 비교 횟수 : (n(n-1))/2 ▷ 각 패스별로 중간 정도에서 부분적인 정렬이 완료되었을 경우 평균 비교 횟수 : (n(n-1))/4 ▷ n개의 레코드를 정렬할 때 n-1번 삽입이 발생되어 전체 수행시간 : O(N2)
■ 메모리 사용 공간
▷별도의 기억 공간을 필요로 하지 않기 때문에, 리스트의 크기 만큼의 기억 공간이 있으면 됨
즉, n개의 레코드 크기만큼의 기억 공간이 있으면 됨
■ 특징
▷ 간단하며, 안정적 ▷ 적은 비교와 많은 교환이 필요한 방법 - 작은 레코드 배열에 가장 유리 ▷ 순서가 틀린 레코드의 순서가 전체 레코드 수에 비해 현저하게 적은 경우 효율적
즉, 원시리스트가 부분적으로 정렬되어 있는 경우에 효과적 ▷ 전체 레코드 수가 20~25 이하인 경우 가장 빠른 정렬 기법 ▷ 매회 서브파일 크기 증가
