삽입 정렬(Insertion Sort)

• 삽입 정렬(Insertion Sort)

i (0<i<n)번째의 요소(tmp)를 순서대로 i-1까지의 정렬된 부분의 알맞은 자리(j)에 삽입하여 정렬

 

void insertion(int a[], int n) {
	int i, j;
	for (i = 1; i < n; i++) {
		int tmp = a[i];
		for (j = i; j > 0 && a[j - 1] > tmp; j--) {
			a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸
		}
		a[j] = tmp; // 찾은 자리 j에 tmp를 넣음
	}
}

 

시간 복잡도: O(n^2) - avg, worst (best는 O(n))