Crate order_stat

Calculate order statistics.

This crates allows one to compute the kth smallest element in (expected) linear time, and estimate a median element via the median-of-medians algorithm.

Source

Installation

Ensure your Cargo.toml contains:

[dependencies]
order-stat = "0.1"

Examples

The kth function allows computing order statistics of slices of Ord types.

let mut v = [4, 1, 3, 2, 0];

println!("the 2nd smallest element is {}", // 1
         order_stat::kth(&mut v, 1));

The kth_by function takes an arbitrary closure, designed for order statistics of slices of floating point and more general comparisons.

let mut v = [4.0, 1.0, 3.0, 2.0, 0.0];

println!("the 3rd smallest element is {}", // 2
         order_stat::kth_by(&mut v, 2, |x, y| x.partial_cmp(y).unwrap()));

#[derive(Debug)]
struct Foo(i32);

let mut v = [Foo(4), Foo(1), Foo(3), Foo(2), Foo(0)];

println!("the element with the 4th smallest field is {:?}", // Foo(3)
         order_stat::kth_by(&mut v, 3, |x, y| x.0.cmp(&y.0)));

The median_of_medians function gives an approximation to the median of a slice of an Ord type.

let mut v = [4, 1, 3, 2, 0];

println!("{} is close to the median",
         order_stat::median_of_medians(&mut v).1);

It also has a median_of_medians_by variant to work with non-Ord types and more general comparisons.

let mut v = [4.0, 1.0, 3.0, 2.0, 0.0];

println!("{} is close to the median",
        order_stat::median_of_medians_by(&mut v, |x, y| x.partial_cmp(y).unwrap()).1);

#[derive(Debug)]
struct Foo(i32);

let mut v = [Foo(4), Foo(1), Foo(3), Foo(2), Foo(0)];

println!("{:?}'s field is close to the median of the fields",
        order_stat::median_of_medians_by(&mut v, |x, y| x.0.cmp(&y.0)).1);

Functions

kth

Compute the kth order statistic (kth smallest element) of array via the Floyd-Rivest Algorithm[1].

kth_by

Compute the element that is the kth order statistic in the ordering defined by cmp (that is, the kth element of array.sort_by(cmp)).

median_of_medians

Calculate an approximate median of array.

median_of_medians_by

Calculate an approximate median of array, using the ordering defined by cmp.