A lightweight crate that brings nth_element to Rust. Available on crates.io.
Be sure that your Cargo.toml looks somewhat like this:
[dependencies]
floydrivest = "0.2.4"Bring the crate into scope:
extern crate floydrivest;
use floydrivest::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.
Link to the original paper with ALGOL60 pseudocode.
Floyd and Rivest’s algorithm for finding the k-th smallest of n elements requires at most n + min(k, n−k) + o(n) comparisons on average and with high probability. Here's the link to another paper.
Here are some benchmarks against other crates: order-stat, kth and pdqlselect. Thanks so much to ilyapopov.
