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.

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