Copyright | (c) 2008-2015 Dan Doel |
---|---|

Maintainer | Dan Doel <dan.doel@gmail.com> |

Stability | Experimental |

Portability | Non-portable (type operators, bang patterns) |

Safe Haskell | None |

Language | Haskell2010 |

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 ()
- sortUniq :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m (v (PrimState m) e)
- sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()
- sortUniqBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m (v (PrimState m) e)
- 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

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

Sorts an entire array using the default ordering.

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

A variant on `sort`

that returns a vector of unique elements.

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

A variant on `sortBy`

which returns a vector of unique elements.

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

Sorts an entire array using a custom ordering returning a vector of the unique elements.

:: (PrimMonad m, MVector v e) | |

=> Comparison e | |

-> v (PrimState m) e | |

-> Int | lower index, l |

-> Int | upper index, u |

-> m () |

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

# Selecting

:: (PrimMonad m, MVector v e, Ord e) | |

=> v (PrimState m) e | |

-> Int | number of elements to select, k |

-> m () |

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

:: (PrimMonad m, MVector v e) | |

=> Comparison e | |

-> v (PrimState m) e | |

-> Int | number 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.

:: (PrimMonad m, MVector v e) | |

=> Comparison e | |

-> v (PrimState m) e | |

-> Int | number of elements to select, k |

-> Int | lower bound, l |

-> Int | upper bound, u |

-> m () |

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

# Partial sorting

:: (PrimMonad m, MVector v e, Ord e) | |

=> v (PrimState m) e | |

-> Int | number of elements to sort, k |

-> m () |

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

:: (PrimMonad m, MVector v e) | |

=> Comparison e | |

-> v (PrimState m) e | |

-> Int | number of elements to sort, k |

-> m () |

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

:: (PrimMonad m, MVector v e) | |

=> Comparison e | |

-> v (PrimState m) e | |

-> Int | number of elements to sort, k |

-> Int | lower index, l |

-> Int | upper index, u |

-> m () |

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

type Comparison e = e -> e -> Ordering Source #

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