stdio-0.2.0.0: A simple and high performance IO toolkit for Haskell

Copyright (c) 2008-2011 Dan Doel (c) Dong Han 2017-2018 BSD winterland1989@gmail.com experimental non-portable None Haskell2010

Std.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 a
Instances

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

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

Constructors

Instances

# merge duplicated

mergeDupAdjacent :: (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

 :: 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

 :: 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

 :: 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.