5일차 (4)

Q10. 단순 삽입 정렬을 배열의 요소 개수가 많아지면 많아질수록 요소 삽입에 필요한 비교, 대입 비용이 무시할 수 없을 정도로 커집니다. 이때 배열에서 이미 정렬된 부분은 이진 검색을 사용할 수 있기 때문에 삽입할 위치를 더 빨리 찾을 수 있습니다. 이진 검색을 사용하여 프로그램을 수정하세요.

정답:

idx = pl <= pr ? pc + 1 : pr + 1;

이 부분이 이해가 잘 안 된다. 우선 정확히 일치하는 a[pc]가 없는 경우에는 break에 어떻게 도달하는지도 궁금하고... 아 pl<=pr 돼도 탈출하는구나 그래서 idx=(pl<=pr)?을 확인하는 거였네. break에 도달해서 탈출했냐 아니면 do while 조건문에 도달해서 탈출했냐 확인하고 만약 break에 도달했다면 pc+1(동일한 데이터의 다음 인덱스), 그리고 do while 조건문에 의해서 탈출한거면 pr+1(정렬된 데이터 내부에는 없다는 뜻이니까) 인덱스를 저장하는 거구나

이해했다. 다음에 또 복습할 땐 풀 수 있을 것 같다.

void insertion(int a[], int n) {
	int j;
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int pl = 0, pr = i-1;
		int pc;
		int idx;
		
		do {
			pc = (pl + pr) / 2;
			if (a[pc] == tmp)  break;
			else if (a[pc] < tmp) pl = pc + 1;
			else pr = pc - 1;
			
		} while (pl <= pr);
		idx = pl <= pr ? pc + 1 : pr + 1;

		for (j = i; j > idx; j--)
			a[j] = a[j - 1];
		a[idx] = tmp;
	}
}