#nth-element #order-statistics #select

floydrivest

A lightweight crate that brings the Floyd-Rivest implementation of nth_element

7 releases

0.2.4 Jan 10, 2021
0.2.3 Jan 10, 2021
0.2.2 Aug 9, 2020
0.1.3 Aug 9, 2020

#1587 in Algorithms

24 downloads per month
Used in 3 crates

MIT license

68KB
163 lines

floydrivest

License: MIT frjnn codecov

A lightweight crate that brings nth_element to Rust. Available on crates.io.

Installation

Be sure that your Cargo.toml looks somewhat like this:

[dependencies]
floydrivest = "0.2.4"

Usage

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.

Implementation

Link to the original paper with ALGOL60 pseudocode.

Performance

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.

Benchmarks

Here are some benchmarks against other crates: order-stat, kth and pdqlselect. Thanks so much to ilyapopov.

benches

No runtime deps