quickselect

[ library, mit, unclassified ] [ Propose Tags ]
Versions [RSS] 0.1.0.0
Change log ChangeLog.md
Dependencies base (>=4 && <5), vector (>=0.7) [details]
License MIT
Copyright 2018 Donnacha Oisín Kidney
Author Donnacha Oisín Kidney
Maintainer mail@doisinkidney.com
Home page https://github.com/oisdk/quickselect#readme
Bug tracker https://github.com/oisdk/quickselect/issues
Source repo head: git clone https://github.com/oisdk/quickselect
Uploaded by oisdk at 2018-05-29T00:02:08Z
Distributions NixOS:0.1.0.0
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 766 total (8 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-05-29 [all 1 reports]

Readme for quickselect-0.1.0.0

[back to package description]

Build Status

quickselect

Haskell implementation of introselect on vectors.

This package provides three selection algorithms on both boxed and unboxed vectors.

The first is quickselect: this is an O(n) selection algorithm, with very fast performance in practice, but an unfortunate O(n^2) worst-case time.

The second is median-of-medians: this has an O(n) worst-case time, but usually performs worse than quickselect in practice.

The final is introselect: this begins as quickselect, but switches to median-of-medians if it realizes it's in one of the pathalogical cases which causes O(n^2) time. It has O(n) worst-case time, and performance in practice very close to quickselect.

There are also machine-generate optimal selection and median-finding functions for inputs of size 3, 4, and 5.