Data.Vector.Algorithms.Quicksort.Median

Documentation

class Median (a :: Type) (b :: Type) (m :: Type -> Type) (s :: Type) | a -> b, m -> s where

Median selection algorithm that, given a vector, should come up with an elements that has good chances to be median (i.e to be greater that half the elements and lower than the other remaining half). The closer to the real median the selected element is, the faster quicksort will run and the better parallelisation will be achieved.

Instance can be declared for specific monad. This is useful if we want to select median at random and need to thread random gen.

Parameter meaning; - a - the median parameter we're defining instance for - b - type of ellements this median selection method is applicable to - m - monad the median selection operates in - s - the same ‘index’ as in ‘ST s’ because vector to be sorted is parameterised and m may need to mention it

Methods

selectMedian

Arguments

:: (MVector v b, Ord b)

=> a

Median algorithm than can carry extra info to be used during median selection (e.g. random generator)

-> v s b

Array

-> m (MedianResult b)

Come up with a median value of a given array

Instances

(PrimMonad m, s ~ PrimState m) => Median (Median3 a) a m s

Defined in Data.Vector.Algorithms.Quicksort.Median

Methods

selectMedian :: (MVector v a, Ord a) => Median3 a -> v s a -> m (MedianResult a)

(PrimMonad m, s ~ PrimState m) => Median (Median3or5 a) a m s

Defined in Data.Vector.Algorithms.Quicksort.Median

Methods

selectMedian :: (MVector v a, Ord a) => Median3or5 a -> v s a -> m (MedianResult a)

data Median3 a

Pick first, last, and the middle elements and find the one that's between the other two, e.g. given elements a, b, and c find y among them that satisfies x <= y <= z.

Constructors

Median3

Instances

(PrimMonad m, s ~ PrimState m) => Median (Median3 a) a m s

Defined in Data.Vector.Algorithms.Quicksort.Median

Methods

selectMedian :: (MVector v a, Ord a) => Median3 a -> v s a -> m (MedianResult a)

data Median3or5 a

Pick first, last, and the middle elements, if all of them are distinct then return median of 3 like Median3 does, otherwise take median of 5 from the already taken 3 and extra 2 elements at 1/4th and 3/4th of array length.

Constructors

Median3or5

Instances

(PrimMonad m, s ~ PrimState m) => Median (Median3or5 a) a m s

Defined in Data.Vector.Algorithms.Quicksort.Median

Methods

selectMedian :: (MVector v a, Ord a) => Median3or5 a -> v s a -> m (MedianResult a)

data MedianResult a

Median selection result.

Constructors

ExistingValue !a !Int

Value that was located at specific index in the original array.