vector-algorithms-0.6.0.3: Efficient algorithms for vector arrays

Portability Non-portable (type operators, bang patterns) Experimental Dan Doel None

Data.Vector.Algorithms.Intro

Contents

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

Sorting

sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()Source

Sorts an entire array using the default ordering.

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

Sorts an entire array using a custom ordering.

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

Sorts a portion of an array [l,u) using a custom ordering

Selecting

select :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()Source

Moves the least k elements to the front of the array in no particular order.

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

Moves the least k elements (as defined by the comparison) to the front of the array in no particular order.

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

Moves the least k elements in the interval [l,u) to the positions [l,k+l) in no particular order.

Partial sorting

partialSort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> Int -> m ()Source

Moves the least k elements to the front of the array, sorted.

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

Moves the least k elements (as defined by the comparison) to the front of the array, sorted.

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

Moves the least k elements in the interval [l,u) to the positions [l,k+l), sorted.

type Comparison e = e -> e -> OrderingSource

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