Median Of Five

December 4, 2012

Our solution requires six comparisons:

(define (median5 lt? a b c d e)
  (when (lt? b a)
    (let ((t a)) (set! a b) (set! b t)))
  (when (lt? e d)
    (let ((t d)) (set! d e) (set! e t)))
  (when (lt? d a)
    (let ((t a)) (set! a d) (set! d t))
    (let ((t b)) (set! b e) (set! e t)))
  (if (lt? b c)
      (if (lt? b d)
          (if (lt? c d) c d)
          (if (lt? b e) b e))
      (if (lt? d c)
          (if (lt? c e) c e)
          (if (lt? b d) b d))))

There is discussion of the algorithm and a brief bit of explanation at http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085.

This function is easy to test: generate all permutations of the list (1 2 3 4 5) and assert that the median of each of them is 3:

> (for-each (lambda (perm) (assert (apply median < perm) 3))
            (permutations '(1 2 3 4 5)))

Testing uses assert from the Standard Prelude, and you can see the complete program, including the permutation generator, at http://programmingpraxis.codepad.org/4CinTQQM.

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 632 other followers

%d bloggers like this: