Expand description
Calculate order statistics.
This crates allows one to compute the k
th smallest element in
(expected) linear time, and estimate a median element via the
median-of-medians algorithm.
§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§
- Compute the
k
th order statistic (k
th smallest element) ofarray
via the Floyd-Rivest Algorithm[1]. - Compute the element that is the
k
th order statistic in the ordering defined bycmp
(that is, thek
th element ofarray.sort_by(cmp)
). - Calculate an approximate median of
array
. - Calculate an approximate median of
array
, using the ordering defined bycmp
.