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.

About these ads

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
            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. [...] today’s Programming Praxis exercise, our goal is to determine to median of five numbers using only six [...]

  3. 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 Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: