in Algorithms edited by
44,239 views
72 votes
72 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
in Algorithms edited by
44.2k views

4 Comments

Tournament method is used.

Ans = $1.5n-2 = 1.5*100 -2 = 150-2 = 148$
4
4
If $n$ is $odd=3$$\left \lfloor \dfrac{n}{2} \right \rfloor$

If $n$ is $even=$ we perform $1$ initial comparison followed by $\dfrac{3}{2}(n-2)$ comparisons, for a total of $\dfrac{3n}{2}-2$ comparisons

$Ans:\dfrac{3\times 100}{2}-2=148$

 

Reference : Chapter 9, Medians and order statistics, cormen.
14
14

Here you go

what kushagra is saying

8
8

14 Answers

0 votes
0 votes

Make pair of elements and compare value in pair, which is greater or which is smaller ?. We have 50 such pairs, then we need 50 comparisons to separate all number in two groups. One group of smaller element from each pair and one group of larger elements from each pair both containing 50 elements each

To find minimum in smaller element group of 50 elements will take 49 comparisons.

To find maximum in greater element group of 50 elements will take 49 comparisons. 

Total comparisons = 50 + 49 + 49 = 148 

 

 

0 votes
0 votes
compare in pairs like- compare arr[0],arr[1] and arr[1],arr[2] ….. total 50 comparisions

for each comparison store bigger one in A list and smaller one in B list

maximum of arr will be in A and min will be in B, finding max in A and min in B each will take 49 comparisions

total 50+49+49=148
Answer:

Related questions