[Algorithm] 삽입 정렬 (Insert Sort)

I. 삽입 정렬 (Insert Sort)의 개요

가. 삽입 정렬의 정의

• 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법

 

나. 삽입 정렬의 특징

• 간단하지만 레코드의 이동이 많은 알고리즘
• 비교적 크기가 작은 데이터 집합 정렬에 유리함.
• 수행시간 복잡도: O(n2)

 

Ⅱ. 삽입 정렬의 단계 및 사례

가. 삽입 정렬의 단계

 

삽입 대상 위치를 2번째부터 마지막까지 지정 비교 대상을 처음부터 바로 전까지 지정 정렬 대상의 값들과 뽑아낸 요소와 비교 삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동 새로 생긴 빈 자리에 해당 요소를 삽입 전체 데이터 집합의 정렬이 완료될 때까지 반복

 

나. 삽입 정렬의 사례

 

void insertion_sort(element list[], int n) { int i, j; element next; for(i = 1; i < n; i++){ next = list[i]; for(j = i - 1; j >= 0 && next.key < list[j].key; j--){ list[j + 1] = list[j]; }; list[j + 1] = next; } }