GeomAlg-0.2.3: Library of geometric algorithms in Haskell Source code Contents Index

GeomAlg.External.OrderStat

Contents An optimal version with O(n) running time. Naive version with O(n log n) running time.

Description

Order statistics, see [CLR90, ch. 10.3]. Warning: The suboptimal algorithm naiveSelect shows a much better real-life performance for many inputs.

Synopsis

selectBy :: (a -> a -> Ordering) -> Int -> [a] -> a select :: Ord a => Int -> [a] -> a medianBy :: (a -> a -> Ordering) -> [a] -> a median :: Ord a => [a] -> a naiveSelectBy :: (a -> a -> Ordering) -> Int -> [a] -> a naiveSelect :: Ord a => Int -> [a] -> a naiveMedianBy :: (a -> a -> Ordering) -> [a] -> a naiveMedian :: Ord a => [a] -> a

An optimal version with O(n) running time.

selectBy :: (a -> a -> Ordering) -> Int -> [a] -> a Source

Select the ith element with respect to the Ordering cmp. The first element has an index of 0. This functions takes O(n) time.

select :: Ord a => Int -> [a] -> a Source

Select with respect to the class Ord, i. e. the function compare.

medianBy :: (a -> a -> Ordering) -> [a] -> a Source

medianBy selects the median of a list with respect to an Ordering relation.

median :: Ord a => [a] -> a Source

Selects the median with respect to Ord.

Naive version with O(n log n) running time.

naiveSelectBy :: (a -> a -> Ordering) -> Int -> [a] -> a Source

The naive version uses !! and sortBy.

naiveSelect :: Ord a => Int -> [a] -> a Source

Naive selection with respect to Ord.

naiveMedianBy :: (a -> a -> Ordering) -> [a] -> a Source

Naive median with respect to the Ordering cmp.

naiveMedian :: Ord a => [a] -> a Source

Naive median with a worst case running time of O(n log n).

Produced by Haddock version 2.4.2