5 개 요소

Question

다음과 같은 질문의 중간은 중간 값을 찾기 위해 필요한 얼마나 많은 최소 비교 크기 5. 의 정렬되지 않은 배열을 감안할 때 최근 마이크로 소프트의 인터뷰

에 질문을 받았다 발견하는? 그 다음 그는 크기 n만큼 그것을 확장했다. 저 항 5 개 요소

용액 6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4] 
a) compare a[1] and a[2] and swap if necessary 
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5] 
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

이 n 개의 요소로 확장 될 수있다. 만약 우리가 O (n)의 n 원소에서 어떻게 중간 선택을 찾을 수 있습니까?

Answer 1

Select 알고리즘은리스트를 5 개의 원소로 나눕니다. (나머지 요소는 이제 무시됩니다.) 그런 다음 5 개 그룹마다 5 개의 값을 레지스터에로드하고 비교 한 경우 6 개 비교 분이면 잠재적으로 매우 빠르게 수행 될 수있는 중간 값이 계산됩니다. 그러면 Select가 n/5 요소의이 하위 목록에서 재귀 적으로 호출되어 실제 중앙값을 찾습니다.