quickselect

[ library, mit, unclassified ] [ Propose Tags ]

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


[Skip to Readme]
Versions [faq] 0.1.0.0
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 Tue May 29 00:02:08 UTC 2018
Distributions NixOS:0.1.0.0
Downloads 288 total (33 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-05-29 [all 1 reports]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


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.