# Crate order_stat [−] [src]

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.

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 `k`th order statistic (`k`th smallest element) of `array` via the Floyd-Rivest Algorithm[1]. kth_by Compute the element that is the `k`th order statistic in the ordering defined by `cmp` (that is, the `k`th 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`.