Function order_stat::kth

pub fn kth<T: Ord>(array: &mut [T], k: usize) -> &mut T

Compute the kth order statistic (kth 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):

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 kth 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 ith smallest of n elements [M1]. Commun. ACM 18, 3, 173. doi:10.1145/360680.360694.

Panics

If k >= array.len(), kth panics.

Examples

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.

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);