삽입 정렬

선택 정렬과 비슷하지만, 좀 더 효율적인 정렬 알고리즘입니다.

배열의 원소를 비교하여, 위치에 삽입하므로 삽입 정렬이라고 불리우며,

최선의 조건에 맞는다면 좋은 효율을 내는 알고리즘입니다.

 

특징

• 제자리 정렬 (다른 메모리 공간이 필요하지 않음)
• 안정 정렬
• 배열의 한 원소 key를 가지고 있고, key를 알맞은 순서에 삽입
• key보다 큰 값은 하나씩 밀어내고, key보다 작은 값은 뒤에 삽입
• 입력 배열이 선정렬(완전하지 않아도)되어있는 경우 효율적인 정렬

시간 복잡도

• 최악: O (n^2)
• 최선: O (n)
• 평균: O (n^2)

최선의 경우에는 좋지만, 대부분의 경우 비 효율적인 편입니다.

예시 그림

구현 코드 ( java )

void insertionSort(int A[], int size) {
	int i, j, key;
	for (int = 1; i < size; i++) {
		key = A[i];
		j = i - 1;
		while(A[j] > key && j >= 0) {
			A[j + 1] = A[j];
				j--;
		}
		A[j + 1] = key;
	}
}