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

4 Responses to “Median Of Five”

  1. Paul said

    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
                return d if d < c else c
            if e > c: 
                e, c = c, e
            if a < e:
                return e if e < b else b
                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. […] today’s Programming Praxis exercise, our goal is to determine to median of five numbers using only six […]

  3. My Haskell solution (see 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 Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: