1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//! 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](https://github.com/huonw/order-stat)
//!
//! # Installation
//!
//! Ensure your `Cargo.toml` contains:
//!
//! ```toml
//! [dependencies]
//! order-stat = "0.1"
//! ```
//!
//! # Examples
//!
//! ```rust
//! let mut v = [4, 1, 3, 2, 0];
//!
//! println!("the 2nd smallest element is {}", order_stat::kth(&mut v, 1));
//! ```
//!
//! ```rust
//! let mut v = [4, 1, 3, 2, 0];
//!
//! println!("{} is close to the median", order_stat::median_of_medians(&mut v).1);
//! ```

#![cfg_attr(all(test, feature = "experimental"), feature(test))]

#[cfg(test)] extern crate rand;
#[cfg(test)] extern crate quickcheck;

mod floyd_rivest;
mod quickselect;
mod mom;

/// Compute the `k`th order statistic (`k`th smallest element) of
/// `array` via the Floyd-Rivest Algorithm[1].
///
/// The return value is the same as that returned by the following
/// function (although the final order of `array` may differ):
///
/// ```rust
/// fn kth_sort<T: Ord>(array: &mut [T], k: usize) -> &mut T {
///     array.sort();
///     &mut array[k]
/// }
/// ```
///
/// That is, `k` is zero-indexed, so the minimum corresponds to `k =
/// 0` and the maximum `k = array.len() - 1`. Furthermore, `array` is
/// mutated, placing the `k`th order statistic into `array[k]` and
/// partitioning the remaining values so that smaller elements lie
/// before and larger after.
///
/// If *n* is the length of `array`, `kth` operates with (expected)
/// running time of *O(n)*, and a single query is usually much faster
/// than sorting `array` (per `kth_sort`). However, if many order
/// statistic queries need to be performed, it may be more efficient
/// to sort and index directly.
///
/// For convenience, a reference to the requested order statistic,
/// `array[k]`, is returned directly. It is also accessibly via
/// `array` itself.
///
/// [1]: Robert W. Floyd and Ronald L. Rivest (1975). Algorithm 489:
/// the algorithm SELECT—for finding the *i*th smallest of *n* elements
/// [M1]. *Commun. ACM* **18**, 3,
/// 173. doi:[10.1145/360680.360694](http://doi.acm.org/10.1145/360680.360694).
///
/// # Panics
///
/// If `k >= array.len()`, `kth` panics.
///
/// # Examples
///
/// ```rust
/// let mut v = [10, 0, -10, 20];
/// let kth = order_stat::kth(&mut v, 2);
///
/// assert_eq!(*kth, 10);
/// ```
///
/// If the order of the original array, or position of the element is
/// important, one can collect references to a temporary before querying.
///
/// ```rust
/// use std::mem;
///
/// let mut v = [10, 0, -10, 20];
///
/// // compute the order statistic of an array of references (the Ord
/// // impl defers to the internals, so this is correct)
/// let kth = *order_stat::kth(&mut v.iter().collect::<Vec<&i32>>(), 2);
///
/// // the position is the difference between the start of the array
/// // and the order statistic's location.
/// let index = (kth as *const _ as usize - &v[0] as *const _ as usize) / mem::size_of_val(&v[0]);
///
/// assert_eq!(*kth, 10);
/// assert_eq!(index, 0);
/// ```
pub fn kth<T: Ord>(array: &mut [T], k: usize) -> &mut T {
    assert!(k < array.len(),
            "order_stat::kth called with k = {} >= len = {}", k, array.len());
    floyd_rivest::select(array, k);
    &mut array[k]
}

pub use mom::median_of_medians;