Data.Select.Unboxed.Median

This module provides an implementation of median-of-medians on unboxed vectors. As a selection algorithm, it has optimal \(\mathcal{O}(n)\) worst-case time, however it is usually beaten in practice by quickselect (which has \(\mathcal{O}(n^2)\) worst-case time). For an algorithm with the same worst-case time, but better general performance, see Data.Select.Unboxed.Intro.

Documentation

selectBy :: Unbox a => (a -> a -> Bool) -> Int -> Vector a -> a

\(\mathcal{O}(n)\). Find the nth item, ordered by the supplied relation.

i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList (xs :: [Int]))

select :: (Unbox a, Ord a) => Int -> Vector a -> a

\(\mathcal{O}(n)\). Find the nth smallest item in the vector.

>>> select 4 (Vector.fromList "this is an example")
'a'

>>> select 3 (Vector.fromList [0,1,4,2,3,5,6]) :: Int
3