Modulevector-algorithms-0.9.1.0Haskell2010

Data.Vector.Algorithms.Optimal

Optimal sorts for very small array sizes, or for small numbers of particular indices in a larger array (to be used, for instance, for sorting a median of 3 values into the lowest position in an array for a median-of-3 quicksort).

1 type
6 values

Packagevector-algorithms-0.9.1.0
Exports7
LanguageHaskell2010
LicenceBSD-3-Clause
SourceOptimal.hs

valuesort2ByIndex

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> Int
-> m ()

Sorts the elements at the two given indices using the comparison. This is essentially a compare-and-swap, although the first index is assumed to be the lower of the two.

valuesort2ByOffset

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> m ()

Sorts the elements at the positions off and 'off + 1' in the given array using the comparison.

valuesort3ByIndex

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> Int
-> Int
-> m ()

Sorts the elements at the three given indices. The indices are assumed to be given from lowest to highest, so if 'l < m < u' then 'sort3ByIndex cmp a m l u' essentially sorts the median of three into the lowest position in the array.

valuesort3ByOffset

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> m ()

Sorts the three elements starting at the given offset in the array.

valuesort4ByIndex

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> Int
-> Int
-> Int
-> m ()

Sorts the elements at the four given indices. Like the 2 and 3 element versions, this assumes that the indices are given in increasing order, so it can be used to sort medians into particular positions and so on.

valuesort4ByOffset

:: (PrimMonad m, MVector v e)
=> Comparison e
-> v (PrimState m) e
-> Int
-> m ()

Sorts the four elements beginning at the offset.

typetype Comparison e = e -> e -> Ordering

A type of comparisons between two values of a given type.