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
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.
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.
Labels:
4 numbers,
sort,
sort 4 numbers in 5 comparisons
Location:
Fairfield, IA, USA
Subscribe to:
Posts (Atom)