quickselect
Downloads
- quickselect-0.1.0.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
| 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 | 838 total (2 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]
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.