frjnn / floydrivest

Rust's nth_element implementation using the Floyd-Rivest algorithm.

floydrivest

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.