## 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

### 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 […]

```median5 :: Ord a => [a] -> a