Data.Select.Quick

This module provides an implementation of quickselect on boxed vectors. It has an average time of \(\mathcal{O}(n)\), but a worst-case time of \(\mathcal{O}(n^2)\). For an algorithm with similar performance but a better worst-case time, see Data.Select.Intro.

Documentation

selectBy :: (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)

select :: 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])
3