Sorts an entire array using the default ordering.
Modulevector-algorithms-0.9.1.0Haskell2010
Data.Vector.Algorithms.Intro
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).
Contents
Synopsis
- value sort
- value sortUniq
- value sortBy
- value sortUniqBy
- value sortByBounds
- value select
- value selectBy
- value selectByBounds
- value partialSort
- value partialSortBy
- value partialSortByBounds
- type Comparison
- Packagevector-algorithms-0.9.1.0
- Exports12
- LanguageHaskell2010
- LicenceBSD-3-Clause
- SourceIntro.hs
Sorting
A variant on sort that returns a vector of unique elements.
A variant on sortBy which returns a vector of unique elements.
Sorts an entire array using a custom ordering returning a vector of the unique elements.
value
sortByBounds Sorts a portion of an array [l,u) using a custom ordering
Selecting
value
select Moves the least k elements to the front of the array in no particular order.
value
selectBy :: (PrimMonad m, MVector v e)=> Comparison e-> v (PrimState m) e-> Intnumber of elements to select, k
-> m ()
Moves the least k elements (as defined by the comparison) to the front of the array in no particular order.
value
selectByBounds Moves the least k elements in the interval [l,u) to the positions [l,k+l) in no particular order.
Partial sorting
value
partialSort Moves the least k elements to the front of the array, sorted.
value
partialSortBy :: (PrimMonad m, MVector v e)=> Comparison e-> v (PrimState m) e-> Intnumber of elements to sort, k
-> m ()
Moves the least k elements (as defined by the comparison) to the front of the array, sorted.
value
partialSortByBounds 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.