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;