삽입 정렬(Insertion Sort)

단순 삽입 정렬

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입

• 삽입 과정

1. 정렬된 열의 왼쪽 끝에 도달
2. tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견 및 교환

• 단순 삽입 알고리즘

void insertion(int a[], int n) {
	int i, j;

	for (i = 1; i < n; i++) { // 전 값과 비교하기 때문에 1인덱스부터 시작
		int tmp = a[i]; // 삽입할 값 저장
		for (j = i; j > 0 && a[j - 1] > tmp; j--) // 삽입할 값의 앞만 검사
			a[j] = a[j - 1]; // 뒤로 한칸씩 옮김
		// memmove(&a[j], &a[j - 1], sizeof(int)); // memory move 위치 이동 함수
		a[j] = tmp; // 알맞은 위치에 삽입
	}
}

• 교환 과정

1. j가 > 0보다 큼
2. a[j - 1] 즉, 그 전 값이 tmp(삽입할 값)보다 클경우 뒤로 한칸씩 옮김(a[j] = a[j - 1])

• 비교 횟수
  n(n - 1)/2 = (n - 1) + (n - 2) + ... + 1
  시간 복잡도 : O(n^2)

• 장점

1. 단순 선택 정렬과 비교해서 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적임
2. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빠름(비교횟수가 적음)

• 단점
  삽입할 위치가 멀리 떨어져 있으면 이동횟수가 많아짐