#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

#873 in Algorithms

Download history 12095/week @ 2024-11-16 13014/week @ 2024-11-23 14131/week @ 2024-11-30 14063/week @ 2024-12-07 13528/week @ 2024-12-14 6210/week @ 2024-12-21 5467/week @ 2024-12-28 12090/week @ 2025-01-04 9259/week @ 2025-01-11 11391/week @ 2025-01-18 14002/week @ 2025-01-25 14336/week @ 2025-02-01 16575/week @ 2025-02-08 16446/week @ 2025-02-15 16712/week @ 2025-02-22 18455/week @ 2025-03-01

70,641 downloads per month
Used in 55 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