adqselect
A lightweight crate that brings to Rust an nth_element
implementation that leverages Andrei Alexandrescu's adaptive quickselect algorithm. Also available on crates.io.
Installation
Be sure that your Cargo.toml
looks somewhat like this:
[]
= "0.1.1"
Usage
Bring the crate into scope:
extern crate adqselect;
use nth_element;
then simply call nth_element
on a vector.
let mut v = vec!;
nth_element;
assert_eq!;
This implementation also handles generic data types as long as they satisfy the PartialEq
and PartialOrd
traits.
Implementation
Link to the original paper: Fast Deterministic Selection by Andrei Alexandrescu.
Performance
The algorithm is based on a refined version of Median of Medians and it guarantees linear deterministic time complexity.
Benchmarks
Here are some benchmarks against other crates: floydrivest, order-stat, kth and pdqselect.