Data.Median.Optimal

This module provides optimal median-finding functions for small, fixed-size inputs. Each function returns the (0-based) index of the argument which is the median, according to the supplied relation.

Documentation

median3 :: (a -> a -> Bool) -> a -> a -> a -> Int

Find the median of 3 items, optimally.

>>> median3 (<=) 1 2 3
1
>>> median3 (<=) 1 3 2
2
>>> median3 (<=) 2 3 1
0

[x,y,z] !! median3 (<=) x y z === sort [x,y,z] !! 1

median4 :: (a -> a -> Bool) -> a -> a -> a -> a -> Int

Find the median of 4 items, optimally.

>>> median4 (<=) 1 4 3 2
2
>>> median4 (<=) 1 3 2 4
1
>>> median4 (<=) 2 4 1 3
3
>>> median4 (<=) 3 1 4 2
0

[w,x,y,z] !! median4 (<=) w x y z `elem` (init.tail.sort) [w,x,y,z]

median5 :: (a -> a -> Bool) -> a -> a -> a -> a -> a -> Int

Find the median of 5 items, optimally.

>>> median5 (<=) 1 4 3 2 5
2
>>> median5 (<=) 1 3 2 4 5
1
>>> median5 (<=) 2 4 1 3 5
3
>>> median5 (<=) 3 1 4 2 5
0
>>> median5 (<=) 2 1 4 5 3
4

[v,w,x,y,z] !! median5 (<=) v w x y z  === sort [v,w,x,y,z] !! 2