#5-3-3 The Art of Computer Programming - 정렬과 검색

이번 절은 최소 비교 선택에 대한 내용이다.

이전 절에서 최소비교 병합에 대해서 알아본 것과 같이 이번에는 선택에 대해 알아본다.

n개의 원소들 중 t번째로 큰 것을 선택하는 가능한 최고의 절차를 찾는 것이라고 보면 된다.

 

탈락식 토너먼트의 응용으로 쓰일 수 있다.

 

원소들이 무작위 순서라는 가정 하에 평균 비교 횟수를 최소화 하는 알고리즘도 필요하다.

다른 경우와 마찬가지로 최소평균이 최소 최대보다 상당히 어렵다.

 

부분 순서가 n개의 정점들로 된, k개의 연결된 구성요소들을 가진 한 비순환 유향 그래프 G로 정의 돈다면, 그러한 문제들을 푸는데 필요한 최소 비교 횟수는 최악의 비교 횟수와 수식으로 정리할 수 있다.