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.3"
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]; 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.