A lightweight crate that brings nth_element to Rust. Available on crates.io.
Be sure that your Cargo.toml looks somewhat like this:
toml
[dependencies]
floydrivest = "0.1.2"
Bring the crate into scope:
```rust extern crate floydrivest;
use floydrivest::nthelement;
``
then simply callnthelement` on a vector.
```rust let mut v = vec![10, 7, 9, 7, 2, 8, 8, 1, 9, 4]; // a vector of i64. let len = v.len();
nth_element(&mut v, 0, len - 1, 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.
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.