[ library, mit, unclassified ] [ Propose Tags ]

Please see the README on Github at https://github.com/oisdk/quickselect#readme

[Skip to Readme]
Versions [faq]
Change log ChangeLog.md
Dependencies base (==4.*), 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:
Downloads 518 total (16 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-05-29 [all 1 reports]




Maintainer's Corner

For package maintainers and hackage trustees

Readme for quickselect-

[back to package description]

Build Status


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.