pair the numbers in groups of two compare them and winner need not be checked for minimum and loser for maximum thus we would get maximum and minimum in
3n/2 -2 comparison
for example let us have an array of a[]={34,21,45,67}
first compare 34 and 21 winner is 34 loser 21
second compare 45 67 winner is 67 loser 45
third compare 67 and 34 (winners of first two) winner is 67 no need to maintain loser
fourth compare 21 45 (losers of first two) loser is 21 no need to maintain winner
we have found the winner is 67 and loser is 21 in just four comparison. You can try it on more numbers
3n/2 -2 comparison
for example let us have an array of a[]={34,21,45,67}
first compare 34 and 21 winner is 34 loser 21
second compare 45 67 winner is 67 loser 45
third compare 67 and 34 (winners of first two) winner is 67 no need to maintain loser
fourth compare 21 45 (losers of first two) loser is 21 no need to maintain winner
we have found the winner is 67 and loser is 21 in just four comparison. You can try it on more numbers
No comments:
Post a Comment