Tuesday, August 9, 2011

How to find median of 5 numbers in 7 comparisons? No other constraints.

Algorithm: findMedian(a, b, c, d, e)
step 1: sort(a, b, c, d) {sort the first four numbers using the sort module in 5 comparisons}
step 2:
if e < b then median <- b else if e > c then median <- c
else median <- e

return median

Total comparisons to sort the first four numbers = 5
Total comparisons to locate median = 2

Therefore total comparisons to find median of four numbers = 5 + 2 = 7

No comments:

Post a Comment