#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
Download history 6994/week @ 2023-12-04 5370/week @ 2023-12-11 4257/week @ 2023-12-18 1346/week @ 2023-12-25 3987/week @ 2024-01-01 6128/week @ 2024-01-08 8619/week @ 2024-01-15 8140/week @ 2024-01-22 9416/week @ 2024-01-29 10414/week @ 2024-02-05 10522/week @ 2024-02-12 10957/week @ 2024-02-19 19896/week @ 2024-02-26 11265/week @ 2024-03-04 10920/week @ 2024-03-11 8538/week @ 2024-03-18

50,759 downloads per month
Used in 36 crates (10 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