5일차 (5)

Q11. Q10의 알고리즘은 삽입할 위치의 검색은 빠르지만 삽입을 위해 요소를 하나씩 뒤쪽으로 미는 작업 비용이 단순 삽입 정렬 알고리즘과 같습니다. 요소를 뒤쪽으로 미는 작업을 표준 라이브러리의 memmove 함수를 사용해서 구현하면 비용을 줄여 좀 더 빠른 속도를 얻을 수 있습니다. 이 아이디어를 바탕으로 이진 삽입 정렬 함수를 수정하세요.

 

우선 memmove부터 찾아봐야겠다.

설명 해석:

source의 num만큼의? 값들을 복사해 destination으로 복사한다.

복사는 중간버퍼를 사용하는데, 이미 데이터가 있다면 덮어 씌워질 수 있다.

source와 destication 포인터가 가리키는 요소의 타입과 이 기능은 관련이 없다.

null 체크는 하지 않고 항상 num bytes 만큼 복사한다.

오버플로우를 피하기 위해서, destination과 source의 사이즈는 최소 num bytes여야 한다.

 

<파라미터>

destination: 복사한 값을 넣기 위한 배열 포인터

source: 복사할 값을 불러오기 위한 배열 포인터

num: copy할 bytes의 수.

 

정답:

설명을 읽어봤을 때 포인터끼리 복사하는 걸로 이해해서(하단의 destination array라고 나와서) 새 임시 배열이 필요한 줄 알았는데...

정답을 보니 그건 아니었나보다. 요소끼리도 변환이 되네... 생각해보면 주소값을 입력하기만 하면 되는 거니 요소의 주소값을 입력하면 되는구나 완전히는 아니지만 이해가 되는 것 같다...

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

	for (int i = 1; i < n; i++) {
		int key = a[i];
		int pl = 0, pr = i - 1;
		int pc;
		int pd;

		do {
			pc = (pl + pr) / 2;
			if (a[pc] == key)  break;
			else if (a[pc] < key) pl = pc + 1;
			else pr = pc - 1;

		} while (pl <= pr);
		pd = (pl <= pr) ? pc + 1 : pr + 1;

		memmove(&a[pd + 1], &a[pd], (i - pd) * sizeof(int));
		a[pd] = key;
	}
}