Z-Data-0.8.6.0: Array, vector and text
Copyright (c) 2008-2011 Dan Doel (c) Dong Han 2017-2018 BSD winterland1989@gmail.com experimental non-portable None Haskell2010

Z.Data.Vector.Sort

Contents

Description

This module provide three stable sorting algorithms, which are:

• mergeSort, a O(log(n)) general-purpose sorting algorithms for all different size vectors.
• insertSort a O(n^2) sorting algorithms suitable for very small vectors.
• radixSort a O(n) sorting algorithms based on Radix instance, which is prefered on large vectors.

Sorting is always performed in ascending order. To reverse the order, either use XXSortBy or use Down, RadixDown newtypes. In general changing comparing functions can be done by creating auxiliary newtypes and Ord instances (make sure you inline instance's method for performence!). Or Radix instances in radixSort case, for example:

data Foo = Foo { key :: Int16, ... }

-- You should add INLINE pragmas to following methods
bucketSize = bucketSize . key
passes = passes . key

Synopsis

# Sort

mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a Source #

O(n*log(n)) Sort vector based on element's Ord instance with classic mergesort algorithm.

This is a stable sort, During sorting two O(n) worker arrays are needed, one of them will be freezed into the result vector. The merge sort only begin at tile size larger than mergeTileSize, each tile will be sorted with insertSort, then iteratively merged into larger array, until all elements are sorted.

mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a Source #

The mergesort tile size, mergeTileSize = 8.

insertSort :: (Vec v a, Ord a) => v a -> v a Source #

O(n^2) Sort vector based on element's Ord instance with simple insertion-sort algorithm.

This is a stable sort. O(n) extra space are needed, which will be freezed into result vector.

insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a Source #

newtype Down a #

The Down type allows you to reverse sort order conveniently. A value of type Down a contains a value of type a (represented as Down a). If a has an Ord instance associated with it then comparing two values thus wrapped will give you the opposite of their normal sort order. This is particularly useful when sorting in generalised list comprehensions, as in: then sortWith by Down x

Since: base-4.6.0.0

Constructors

 Down FieldsgetDown :: aSince: base-4.14.0.0

#### Instances

Instances details
 Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methods(>>=) :: Down a -> (a -> Down b) -> Down b #(>>) :: Down a -> Down b -> Down b #return :: a -> Down a # Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methodsfmap :: (a -> b) -> Down a -> Down b #(<\$) :: a -> Down b -> Down a # Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methodspure :: a -> Down a #(<*>) :: Down (a -> b) -> Down a -> Down b #liftA2 :: (a -> b -> c) -> Down a -> Down b -> Down c #(*>) :: Down a -> Down b -> Down b #(<*) :: Down a -> Down b -> Down a # Since: base-4.12.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Down m -> m #foldMap :: Monoid m => (a -> m) -> Down a -> m #foldMap' :: Monoid m => (a -> m) -> Down a -> m #foldr :: (a -> b -> b) -> b -> Down a -> b #foldr' :: (a -> b -> b) -> b -> Down a -> b #foldl :: (b -> a -> b) -> b -> Down a -> b #foldl' :: (b -> a -> b) -> b -> Down a -> b #foldr1 :: (a -> a -> a) -> Down a -> a #foldl1 :: (a -> a -> a) -> Down a -> a #toList :: Down a -> [a] #null :: Down a -> Bool #length :: Down a -> Int #elem :: Eq a => a -> Down a -> Bool #maximum :: Ord a => Down a -> a #minimum :: Ord a => Down a -> a #sum :: Num a => Down a -> a #product :: Num a => Down a -> a # Since: base-4.12.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Down a -> f (Down b) #sequenceA :: Applicative f => Down (f a) -> f (Down a) #mapM :: Monad m => (a -> m b) -> Down a -> m (Down b) #sequence :: Monad m => Down (m a) -> m (Down a) # Since: base-4.12.0.0 Instance detailsDefined in Data.Functor.Classes MethodsliftEq :: (a -> b -> Bool) -> Down a -> Down b -> Bool # Since: base-4.12.0.0 Instance detailsDefined in Data.Functor.Classes MethodsliftCompare :: (a -> b -> Ordering) -> Down a -> Down b -> Ordering # Since: base-4.12.0.0 Instance detailsDefined in Data.Functor.Classes MethodsliftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Down a) #liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Down a] #liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Down a) #liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Down a] # Since: base-4.12.0.0 Instance detailsDefined in Data.Functor.Classes MethodsliftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Down a -> ShowS #liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Down a] -> ShowS # Since: deepseq-1.4.3.0 Instance detailsDefined in Control.DeepSeq MethodsliftRnf :: (a -> ()) -> Down a -> () # Unbox a => Vector Vector (Down a) Instance detailsDefined in Data.Vector.Unboxed.Base MethodsbasicUnsafeFreeze :: PrimMonad m => Mutable Vector (PrimState m) (Down a) -> m (Vector (Down a)) #basicUnsafeThaw :: PrimMonad m => Vector (Down a) -> m (Mutable Vector (PrimState m) (Down a)) #basicLength :: Vector (Down a) -> Int #basicUnsafeSlice :: Int -> Int -> Vector (Down a) -> Vector (Down a) #basicUnsafeIndexM :: Monad m => Vector (Down a) -> Int -> m (Down a) #basicUnsafeCopy :: PrimMonad m => Mutable Vector (PrimState m) (Down a) -> Vector (Down a) -> m () #elemseq :: Vector (Down a) -> Down a -> b -> b # Unbox a => MVector MVector (Down a) Instance detailsDefined in Data.Vector.Unboxed.Base MethodsbasicLength :: MVector s (Down a) -> Int #basicUnsafeSlice :: Int -> Int -> MVector s (Down a) -> MVector s (Down a) #basicOverlaps :: MVector s (Down a) -> MVector s (Down a) -> Bool #basicUnsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) (Down a)) #basicInitialize :: PrimMonad m => MVector (PrimState m) (Down a) -> m () #basicUnsafeReplicate :: PrimMonad m => Int -> Down a -> m (MVector (PrimState m) (Down a)) #basicUnsafeRead :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> m (Down a) #basicUnsafeWrite :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> Down a -> m () #basicClear :: PrimMonad m => MVector (PrimState m) (Down a) -> m () #basicSet :: PrimMonad m => MVector (PrimState m) (Down a) -> Down a -> m () #basicUnsafeCopy :: PrimMonad m => MVector (PrimState m) (Down a) -> MVector (PrimState m) (Down a) -> m () #basicUnsafeMove :: PrimMonad m => MVector (PrimState m) (Down a) -> MVector (PrimState m) (Down a) -> m () #basicUnsafeGrow :: PrimMonad m => MVector (PrimState m) (Down a) -> Int -> m (MVector (PrimState m) (Down a)) # Bounded a => Bounded (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methods Enum a => Enum (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methodssucc :: Down a -> Down a #pred :: Down a -> Down a #toEnum :: Int -> Down a #fromEnum :: Down a -> Int #enumFrom :: Down a -> [Down a] #enumFromThen :: Down a -> Down a -> [Down a] #enumFromTo :: Down a -> Down a -> [Down a] #enumFromThenTo :: Down a -> Down a -> Down a -> [Down a] # Eq a => Eq (Down a) Since: base-4.6.0.0 Instance detailsDefined in Data.Ord Methods(==) :: Down a -> Down a -> Bool #(/=) :: Down a -> Down a -> Bool # Floating a => Floating (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methodspi :: Down a #exp :: Down a -> Down a #log :: Down a -> Down a #sqrt :: Down a -> Down a #(**) :: Down a -> Down a -> Down a #logBase :: Down a -> Down a -> Down a #sin :: Down a -> Down a #cos :: Down a -> Down a #tan :: Down a -> Down a #asin :: Down a -> Down a #acos :: Down a -> Down a #atan :: Down a -> Down a #sinh :: Down a -> Down a #cosh :: Down a -> Down a #tanh :: Down a -> Down a #asinh :: Down a -> Down a #acosh :: Down a -> Down a #atanh :: Down a -> Down a #log1p :: Down a -> Down a #expm1 :: Down a -> Down a #log1pexp :: Down a -> Down a #log1mexp :: Down a -> Down a # Fractional a => Fractional (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methods(/) :: Down a -> Down a -> Down a #recip :: Down a -> Down a # Integral a => Integral (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methodsquot :: Down a -> Down a -> Down a #rem :: Down a -> Down a -> Down a #div :: Down a -> Down a -> Down a #mod :: Down a -> Down a -> Down a #quotRem :: Down a -> Down a -> (Down a, Down a) #divMod :: Down a -> Down a -> (Down a, Down a) #toInteger :: Down a -> Integer # Data a => Data (Down a) Since: base-4.12.0.0 Instance detailsDefined in Data.Data Methodsgfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Down a -> c (Down a) #gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Down a) #toConstr :: Down a -> Constr #dataTypeOf :: Down a -> DataType #dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Down a)) #dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Down a)) #gmapT :: (forall b. Data b => b -> b) -> Down a -> Down a #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r #gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r #gmapQ :: (forall d. Data d => d -> u) -> Down a -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> Down a -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # Num a => Num (Down a) Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methods(+) :: Down a -> Down a -> Down a #(-) :: Down a -> Down a -> Down a #(*) :: Down a -> Down a -> Down a #negate :: Down a -> Down a #abs :: Down a -> Down a #signum :: Down a -> Down a # Ord a => Ord (Down a) Since: base-4.6.0.0 Instance detailsDefined in Data.Ord Methodscompare :: Down a -> Down a -> Ordering #(<) :: Down a -> Down a -> Bool #(<=) :: Down a -> Down a -> Bool #(>) :: Down a -> Down a -> Bool #(>=) :: Down a -> Down a -> Bool #max :: Down a -> Down a -> Down a #min :: Down a -> Down a -> Down a # Read a => Read (Down a) This instance would be equivalent to the derived instances of the Down newtype if the getDown field were removedSince: base-4.7.0.0 Instance detailsDefined in Data.Ord MethodsreadsPrec :: Int -> ReadS (Down a) #readList :: ReadS [Down a] # Real a => Real (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord MethodstoRational :: Down a -> Rational # RealFloat a => RealFloat (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord MethodsfloatRadix :: Down a -> Integer #floatDigits :: Down a -> Int #floatRange :: Down a -> (Int, Int) #decodeFloat :: Down a -> (Integer, Int) #encodeFloat :: Integer -> Int -> Down a #exponent :: Down a -> Int #significand :: Down a -> Down a #scaleFloat :: Int -> Down a -> Down a #isNaN :: Down a -> Bool #isInfinite :: Down a -> Bool #isDenormalized :: Down a -> Bool #isNegativeZero :: Down a -> Bool #isIEEE :: Down a -> Bool #atan2 :: Down a -> Down a -> Down a # RealFrac a => RealFrac (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord MethodsproperFraction :: Integral b => Down a -> (b, Down a) #truncate :: Integral b => Down a -> b #round :: Integral b => Down a -> b #ceiling :: Integral b => Down a -> b #floor :: Integral b => Down a -> b # Show a => Show (Down a) This instance would be equivalent to the derived instances of the Down newtype if the getDown field were removedSince: base-4.7.0.0 Instance detailsDefined in Data.Ord MethodsshowsPrec :: Int -> Down a -> ShowS #show :: Down a -> String #showList :: [Down a] -> ShowS # Ix a => Ix (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methodsrange :: (Down a, Down a) -> [Down a] #index :: (Down a, Down a) -> Down a -> Int #unsafeIndex :: (Down a, Down a) -> Down a -> Int #inRange :: (Down a, Down a) -> Down a -> Bool #rangeSize :: (Down a, Down a) -> Int #unsafeRangeSize :: (Down a, Down a) -> Int # Generic (Down a) Since: base-4.12.0.0 Instance detailsDefined in GHC.Generics Associated Typestype Rep (Down a) :: Type -> Type # Methodsfrom :: Down a -> Rep (Down a) x #to :: Rep (Down a) x -> Down a # Semigroup a => Semigroup (Down a) Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methods(<>) :: Down a -> Down a -> Down a #sconcat :: NonEmpty (Down a) -> Down a #stimes :: Integral b => b -> Down a -> Down a # Monoid a => Monoid (Down a) Since: base-4.11.0.0 Instance detailsDefined in Data.Ord Methodsmempty :: Down a #mappend :: Down a -> Down a -> Down a #mconcat :: [Down a] -> Down a # Storable a => Storable (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord MethodssizeOf :: Down a -> Int #alignment :: Down a -> Int #peekElemOff :: Ptr (Down a) -> Int -> IO (Down a) #pokeElemOff :: Ptr (Down a) -> Int -> Down a -> IO () #peekByteOff :: Ptr b -> Int -> IO (Down a) #pokeByteOff :: Ptr b -> Int -> Down a -> IO () #peek :: Ptr (Down a) -> IO (Down a) #poke :: Ptr (Down a) -> Down a -> IO () # Bits a => Bits (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord Methods(.&.) :: Down a -> Down a -> Down a #(.|.) :: Down a -> Down a -> Down a #xor :: Down a -> Down a -> Down a #complement :: Down a -> Down a #shift :: Down a -> Int -> Down a #rotate :: Down a -> Int -> Down a #bit :: Int -> Down a #setBit :: Down a -> Int -> Down a #clearBit :: Down a -> Int -> Down a #complementBit :: Down a -> Int -> Down a #testBit :: Down a -> Int -> Bool #bitSize :: Down a -> Int #isSigned :: Down a -> Bool #shiftL :: Down a -> Int -> Down a #unsafeShiftL :: Down a -> Int -> Down a #shiftR :: Down a -> Int -> Down a #unsafeShiftR :: Down a -> Int -> Down a #rotateL :: Down a -> Int -> Down a #rotateR :: Down a -> Int -> Down a #popCount :: Down a -> Int # FiniteBits a => FiniteBits (Down a) Since: base-4.14.0.0 Instance detailsDefined in Data.Ord MethodsfiniteBitSize :: Down a -> Int # NFData a => NFData (Down a) Since: deepseq-1.4.0.0 Instance detailsDefined in Control.DeepSeq Methodsrnf :: Down a -> () # Prim a => Prim (Down a) Since: primitive-0.6.5.0 Instance detailsDefined in Data.Primitive.Types MethodssizeOf# :: Down a -> Int# #alignment# :: Down a -> Int# #readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Down a #) #writeByteArray# :: MutableByteArray# s -> Int# -> Down a -> State# s -> State# s #setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Down a -> State# s -> State# s #indexOffAddr# :: Addr# -> Int# -> Down a #readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Down a #) #writeOffAddr# :: Addr# -> Int# -> Down a -> State# s -> State# s #setOffAddr# :: Addr# -> Int# -> Int# -> Down a -> State# s -> State# s # Unbox a => Unbox (Down a) Instance detailsDefined in Data.Vector.Unboxed.Base Since: base-4.12.0.0 Instance detailsDefined in GHC.Generics Associated Typestype Rep1 Down :: k -> Type # Methodsfrom1 :: forall (a :: k). Down a -> Rep1 Down a #to1 :: forall (a :: k). Rep1 Down a -> Down a # newtype MVector s (Down a) Instance detailsDefined in Data.Vector.Unboxed.Base newtype MVector s (Down a) = MV_Down (MVector s a) type Rep (Down a) Instance detailsDefined in GHC.Generics type Rep (Down a) = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) newtype Vector (Down a) Instance detailsDefined in Data.Vector.Unboxed.Base newtype Vector (Down a) = V_Down (Vector a) type Rep1 Down Instance detailsDefined in GHC.Generics type Rep1 Down = D1 ('MetaData "Down" "Data.Ord" "base" 'True) (C1 ('MetaCons "Down" 'PrefixI 'True) (S1 ('MetaSel ('Just "getDown") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1))

radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a Source #

O(n) Sort vector based on element's Radix instance with radix-sort, (Least significant digit radix sorts variation).

This is a stable sort, one or two extra O(n) worker array are need depend on how many passes shall be performed, and a bucketSize counting bucket are also needed. This sort algorithms performed extremly well on small byte size types such as Int8 or Word8, while on larger type, constant passes may render this algorithm not suitable for small vectors (turning point around 2^(2*passes)).

class Radix a where Source #

Types contain radixs, which can be inspected with radix during different passes.

The default instances share a same bucketSize 256, which seems to be a good default.

Methods

bucketSize :: a -> Int Source #

The size of an auxiliary array, i.e. the counting bucket

passes :: a -> Int Source #

The number of passes necessary to sort an array of es, it equals to the key's byte number.

radixLSB :: a -> Int Source #

The radix function used in the first pass, works on the least significant bit.

radix :: Int -> a -> Int Source #

The radix function parameterized by the current pass (0 < pass < passes e-1).

radixMSB :: a -> Int Source #

The radix function used in the last pass, works on the most significant bit.

#### Instances

Instances details

Similar to Down newtype for Ord, this newtype can inverse the order of a Radix instance when used in radixSort.

Constructors

#### Instances

Instances details

# merge duplicated

mergeDupAdjacent :: forall v a. (Vec v a, Eq a) => v a -> v a Source #

merge duplicated adjacent element, prefer left element.

Use this function on a sorted vector will have the same effects as nub.

Arguments

 :: forall v a. Vec v a => (a -> a -> Bool) equality tester,  left right -> eq left right -> v a -> v a

Merge duplicated adjacent element, prefer left element.

Arguments

 :: forall v a. Vec v a => (a -> a -> Bool) equality tester,  left right -> eq left right -> v a -> v a

Merge duplicated adjacent element, prefer right element.

Arguments

 :: forall v a. Vec v a => (a -> a -> Bool) equality tester,  left right -> eq left right -> (a -> a -> a) the merger,  left right -> merge left right -> v a -> v a

Merge duplicated adjacent element, based on a equality tester and a merger function.