Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Selection algorithm in Haskell
module SelectBy (selectBy, medianBy, select, median)
where
import Data.List
splitEvery _ [] = []
splitEvery n xs = xn : splitEvery n r
where (xn, r) = splitAt n xs
-- | O(n) kth smallest selection
selectBy :: (a -> a -> Ordering) -> Int -> [a] -> a
selectBy c k xs
| k >= length xs = maximumBy c xs
| k == 0 = minimumBy c xs
| null . drop 10 $ xs = sortBy c xs !! k
| k <= ll = selectBy c k l
| k > le = selectBy c (k - le) g
| otherwise = m
where ms = map (selectBy c 3) . splitEvery 5 $ xs
m = medianBy c ms
l = filter ((GT ==) . c m) xs
ll = length l
e = filter ((EQ ==) . c m) xs
le = length e + ll
g = filter ((LT ==) . c m) xs
medianBy :: (a -> a -> Ordering) -> [a] -> a
medianBy c xs = selectBy c (length xs `div` 2) xs
select :: Ord a => Int -> [a] -> a
select = selectBy compare
median :: Ord a => [a] -> a
median = medianBy compare
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.