|
Data.Vector.Algorithms.Intro | Portability | Non-portable (type operators, bang patterns) | Stability | Experimental | Maintainer | Dan Doel <dan.doel@gmail.com> |
|
|
|
|
|
Description |
This module implements various algorithms based on the introsort algorithm,
originally described by David R. Musser in the paper /Introspective Sorting
and Selection Algorithms/. It is also in widespread practical use, as the
standard unstable sort used in the C++ Standard Template Library.
Introsort is at its core a quicksort. The version implemented here has the
following optimizations that make it perform better in practice:
- Small segments of the array are left unsorted until a final insertion
sort pass. This is faster than recursing all the way down to
one-element arrays.
- The pivot for segment [l,u) is chosen as the median of the elements at
l, u-1 and (u+l)/2. This yields good behavior on mostly sorted (or
reverse-sorted) arrays.
- The algorithm tracks its recursion depth, and if it decides it is
taking too long (depth greater than 2 * lg n), it switches to a heap
sort to maintain O(n lg n) worst case behavior. (This is what makes the
algorithm introsort).
|
|
Synopsis |
|
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m () | | sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m () | | sortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> m () | | select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m () | | selectBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m () | | selectByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m () | | partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m () | | partialSortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> m () | | partialSortByBounds :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m () | | type Comparison e = e -> e -> Ordering |
|
|
|
Sorting
|
|
|
Sorts an entire array using the default ordering.
|
|
|
Sorts an entire array using a custom ordering.
|
|
|
Sorts a portion of an array [l,u) using a custom ordering
|
|
Selecting
|
|
|
Moves the least k elements to the front of the array in
no particular order.
|
|
|
Moves the least k elements (as defined by the comparison) to
the front of the array in no particular order.
|
|
|
Moves the least k elements in the interval [l,u) to the positions
[l,k+l) in no particular order.
|
|
Partial sorting
|
|
|
Moves the least k elements to the front of the array, sorted.
|
|
|
Moves the least k elements (as defined by the comparison) to
the front of the array, sorted.
|
|
|
Moves the least k elements in the interval [l,u) to the positions
[l,k+l), sorted.
|
|
|
A type of comparisons between two values of a given type.
|
|
Produced by Haddock version 2.4.2 |