삽입 정렬은 항상 정렬 된 목록에서 N-1 비교를 취하십니까?

Question

방금 오래된 "정렬 탐정"숙제 (검은 색 상자 정렬 알고리즘이 주어지며 결과에 의한 어떤 예제를 결정해야합니다)를 마쳤습니다. 삽입 정렬은 항상 N-1 비교를 취했습니다.정렬 된 목록에서.모든 사람이 과제를 해제 할 때까지 강사의 코드를 볼 수 없으므로 문제를 해결할 수있는 방법에 대해 다른 학생들에게 팁을 줄 수있는 수업에서 질문을 할 수 있습니다.질문이 있으므로 적어도 주 에이 질문에 대한 답변을 얻을 수 없습니다.

는 항상 정렬 된 목록에서 삽입 정렬의 교과서 예제가 N-1 비교를 할 수있는 실제 세계에서 또는 강사의 / 교과서의 삽입 종류의 버전의 곡선인가요?

Google과 Wikipedia를 검색 한 후에, 나는 이것에 대한 답변을 찾을 수 없었습니다. 즉, 잘못된 질문을하는 것을 의미하거나 그냥 가지고 있지 않습니다.어떤 아이디어도 있습니까?

Answer 1

예, "교과서"삽입 정렬은 입력이 이미 정렬 된 경우 N-1 비교를 수행합니다. 예를 들어 KNuth의 컴퓨터 프로그래밍의 기술, 볼륨 3, §5.2.1, 알고리즘 S ( 직선 삽입 정렬 )의 기술을 참조하십시오. 각 레코드 R _{i (i> 1)에 대해, 알고리즘은 요소 R i-1 아래로 1 로 1 으로 비교합니다. , i 보다 작은 요소를 찾을 때까지. 입력이 이미 정렬 된 경우 R I-1 는 항상 R i 보다 작으므로 알고리즘은 레코드 당 하나의 비교를 수행합니다 (레코드 1의 비교가 없음). .}

물론 R _{1 에서 R i-1 에서 i-1 에서 에서 n * (n- 1) / 2 입력 목록이 이미 정렬 된 경우 비교합니다. 그렇게하지 마십시오. :)}

이진 검색을 사용하여 각 레코드를 삽입 할 위치를 찾을 수도 있습니다. 이를 바이너리 삽입 이라고하며 KNuth는 §5.2.1에서도 설명합니다. 다시 말하지만, 교과서 직선 삽입보다 이미 정렬 된 입력에 대해 더 많은 비교를 수행합니다 (그러나 임의의 입력에서는 더 적습니다).