Crate kth [−] [src]
Algorithms to find the K-th order element
The k-th order element is the element which would be at the k-th index if the array was sorted.
Finding the median is a special case of finding the k-th order element, to find the median, select k to be half the array length.
Partitioning is commonly performed when searching for the K-th order element. An array is partitioned if all elements before a given element X are less than X, and all elements after a that same element X are greater than X.
Example
use kth::SliceExtKth; let mut x = [6, 6, 8 ,1, 2]; // sorted = 1 2 6 6 8 let m = x.len()/2; x.partition_by_kth(m); println!("Median is {}", x[m]); assert_eq!(x[x.len()/2], 6);
Traits
SliceExtKth |
Add k-th order element operations to slices. |