uvector-algorithms-0.2: Efficient algorithms for uvector unboxed arrays

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

Data.Array.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 :: (UA e, Ord e) => MUArr e s -> ST s ()Source

Sorts an entire array using the default ordering.

sortBy :: UA e => Comparison e -> MUArr e s -> ST s ()Source

Sorts an entire array using a custom ordering.

sortByBounds :: UA e => Comparison e -> MUArr e s -> Int -> Int -> ST s ()Source

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

# Selecting

select :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()Source

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

selectBy :: UA e => Comparison e -> MUArr e s -> Int -> ST s ()Source

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

selectByBounds :: UA e => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()Source

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

# Partial sorting

partialSort :: (UA e, Ord e) => MUArr e s -> Int -> ST s ()Source

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

partialSortBy :: UA e => Comparison e -> MUArr e s -> Int -> ST s ()Source

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

partialSortByBounds :: UA e => Comparison e -> MUArr e s -> Int -> Int -> Int -> ST s ()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.