public
Created

Selection algorithm in Haskell

  • Download Gist
SelectBy.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.