개념
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 위치를 찾아 삽입하는 정렬 알고리즘
최악 시간복잡도 : 비교 - O(n^2) 교환 - O(n^2)
최선 시간복잡도 : 비교 - O(n) 교환 - O(1)
평균 시간복잡도 : 비교 - O(n^2) 교환 - O(n^2)
선택 정렬이나 거품 정렬과 같은 알고리즘에 비하면 빠르고, 안정정렬이다.
방법
빨간 원소 : 삽입할 위치를 찾는 원소
회색 원소 : 삽입할 위치가 있는 배열
회색 원소의 제일 뒤 부터 차례대로 비교해가며 빨간 원소가 들어갈 수 있는 자리를 찾는다.
코드
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){
int temp = arr[index];
int aux = index - 1;
while( (aux >= 0) && ( arr[aux] > temp ) ) {
arr[aux + 1] = arr[aux];
aux--;
}
arr[aux + 1] = temp;
}
}