#order-statistics #median-of-medians #partial-sort

order-stat

Compute order statistics efficiently via the Floyd-Rivest algorithm and estimate a median via the median-of-medians algorithm

3 releases

Uses old Rust 2015

0.1.3 Apr 23, 2016
0.1.2 Apr 26, 2015
0.1.1 Apr 25, 2015
0.1.0 Apr 24, 2015

#769 in Algorithms

Download history 24002/week @ 2024-07-24 19547/week @ 2024-07-31 17763/week @ 2024-08-07 22814/week @ 2024-08-14 23964/week @ 2024-08-21 21644/week @ 2024-08-28 16967/week @ 2024-09-04 19659/week @ 2024-09-11 15425/week @ 2024-09-18 20658/week @ 2024-09-25 17442/week @ 2024-10-02 19983/week @ 2024-10-09 19780/week @ 2024-10-16 20455/week @ 2024-10-23 10046/week @ 2024-10-30 10663/week @ 2024-11-06

65,301 downloads per month
Used in 52 crates (11 directly)

MIT/Apache

20KB
345 lines

order-stat

Build Status

Compute order statistics and median-of-medians.

Documentation, crates.io.


lib.rs:

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);

No runtime deps