| Copyright | (c) 2011 Dan Doel |
|---|---|
| Maintainer | Dan Doel <dan.doel@gmail.com> |
| Stability | Experimental |
| Portability | Non-portable (FlexibleContexts, ScopedTypeVariables) |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Vector.Algorithms.AmericanFlag
Description
This module implements American flag sort: an in-place, unstable, bucket sort. Also in contrast to radix sort, the values are inspected in a big endian order, and buckets are sorted via recursive splitting. This, however, makes it sensible for sorting strings in lexicographic order (provided indexing is fast).
The algorithm works as follows: at each stage, the array is looped over, counting the number of elements for each bucket. Then, starting at the beginning of the array, elements are permuted in place to reside in the proper bucket, following chains until they reach back to the current base index. Finally, each bucket is sorted recursively. This lends itself well to the aforementioned variable-length strings, and so the algorithm takes a stopping predicate, which is given a representative of the stripe, rather than running for a set number of iterations.
Documentation
sort :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e) => v (PrimState m) e -> m () Source
Sorts an array using the default ordering. Both Lexicographic and Ord are necessary because the algorithm falls back to insertion sort for sufficiently small arrays.
Arguments
| :: (PrimMonad m, MVector v e) | |
| => Comparison e | a comparison for the insertion sort flalback |
| -> (e -> Int -> Bool) | determines whether a stripe is complete |
| -> Int | the number of buckets necessary |
| -> (Int -> e -> Int) | the big-endian radix function |
| -> v (PrimState m) e | the array to be sorted |
| -> m () |
A fully parameterized version of the sorting algorithm. Again, this function takes both radix information and a comparison, because the algorithms falls back to insertion sort for small arrays.
class Lexicographic e where Source
The methods of this class specify the information necessary to sort
arrays using the default ordering. The name Lexicographic is meant
to convey that index should return results in a similar way to indexing
into a string.
Methods
terminate :: e -> Int -> Bool Source
Given a representative of a stripe and an index number, this function should determine whether to stop sorting.
The size of the bucket array necessary for sorting es
index :: Int -> e -> Int Source
Determines which bucket a given element should inhabit for a particular iteration.