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

How to sort four numbers in 5 comparisons? Efficiency in terms of space, time and number of assignments is not considered.

Algorithm: sort(a, b, c, d)
if a > b then swap(a, b)
if c > d then swap(c, d)
if a > c then swap(a, c)
if b > d then swap(b, d)
if b > c then swap(b, c)

subroutine: swap(x, y)
temp <- x
x <- y
y <- temp

The resulting sequence a, b, c, d will be sorted in ascending order.