#median #partition #select #no-std #nth-element

no-std kth

Find the k-th order element of an array (one of which is the median)

1 unstable release

Uses old Rust 2015

0.1.0 May 29, 2017

#22 in #median

Download history 77/week @ 2024-11-17 30/week @ 2024-11-24 167/week @ 2024-12-01 85/week @ 2024-12-08 79/week @ 2024-12-15 1/week @ 2024-12-22 23/week @ 2024-12-29 81/week @ 2025-01-05 100/week @ 2025-01-12 108/week @ 2025-01-19 82/week @ 2025-01-26 67/week @ 2025-02-02 56/week @ 2025-02-09 81/week @ 2025-02-16 135/week @ 2025-02-23 127/week @ 2025-03-02

408 downloads per month
Used in 3 crates

Apache-2.0 OR MIT

18KB
340 lines

kth

Methods for partitioning arrays & finding the k-th order element.

The median is the element with order equal to half of the array length.

crates.io

travis-ci

docs (release)

docs (master)

Rust RFC issue #1470 talks about adding a similar interface.


lib.rs:

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

Dependencies

~25KB