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:

[dependencies]
adqselect = "0.1.3"

Usage

Bring the crate into scope:

extern crate adqselect;

use adqselect::nth_element;

then simply call nth_element on a vector.

let mut v = vec![10, 7, 9, 7, 2, 8, 8, 1, 9, 4];
nth_element(&mut v, 3, &mut Ord::cmp);

assert_eq!(v[3], 7);

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.

Results

Violin Plot

This chart shows the relationship between function/parameter and iteration time. The thickness of the shaded region indicates the probability that a measurement of the given function/parameter would take a particular length of time.