Median Of Five

December 4, 2012

In the previous exercise we computed the median of five items by sorting them and then taking the third item. Sorting does more work than is necessary; for instance, given the list [1, 2, 3, 5, 4], we don’t need to swap 5 and 4 into their correct positions to determine that 3 is the median as long as we know that both 4 and 5 are greater than 3..

Your task is to write a function that determines the median of five items using the fewest possible comparisons. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “Median Of Five”

  1. Paul said
    December 4, 2012 at 9:21 AM

    I made thos Python version already for the previous exercise, but did not post it.

    import itertools 

def median5(L, key=None):
    """Return a median of L using 6 comparisons              
    """
    a, b, c, d, e = [key(x) for x in L] if key else L          
    if a > b: 
        a, b = b, a
    if d > e: 
        d, e = e, d
    if a < d:
        if b > c: 
            b, c = c, b
        if d < b:
            return b if b < e else e
        else:
            return d if d < c else c
    else:
        if e > c: 
            e, c = c, e
        if a < e:
            return e if e < b else b
        else:
            return a if a < c else c
                
L = [1,2,3,4,5]
for p in itertools.permutations(L, 5):
    assert 3 == median5(p)
print "OK"
  2. Programming Praxis – Median Of Five « Bonsai Code said
    December 4, 2012 at 10:17 AM

    […] today’s Programming Praxis exercise, our goal is to determine to median of five numbers using only six […]

  3. Remco Niemeijer said
    December 4, 2012 at 10:17 AM

    My Haskell solution (see http://bonsaicode.wordpress.com/2012/12/04/programming-praxis-median-of-five/ for a version with comments):

    median5 :: Ord a => [a] -> a
median5 ~[a',b',c,d',e'] = case (b<c, b<d, d<c) of
        (True, True , _    ) -> min c d
        (True, False, _    ) -> min b e
        (False, _   , True ) -> min c e
        (False, _   , False) -> min b d
    where ((_,b), (d,e)) = order (order a' b') (order d' e')
          order x y = if y < x then (y,x) else (x,y)

Leave a comment