2 releases
0.1.1 | Nov 15, 2021 |
---|---|
0.1.0 | Oct 20, 2017 |
#505 in Algorithms
30,813 downloads per month
Used in 121 crates
(9 directly)
43KB
440 lines
A quickselect algorithm adapted from Rust's implementation of the pdqsort algorithm.
NOTE: you may want to use Rust's official version of this algorithm, select_nth_unstable_by
lib.rs
:
Pattern-defeating quickselect
The algorithm is based on pattern-defeating quicksort by Orson Peters, published at:
https://github.com/orlp/pdqsort
It is also heavily adapted from the Rust implementation of pdqsort
(https://github.com/stjepang/pdqsort) and Rust's own slice::sort_unstable
.
NOTE: you may want to use Rust's official version of this algorithm,
slice::select_nth_unstable_by
Properties
- Best-case running time is
O(n)
. - Worst-case running time is
O(n log n)
. - Does not allocate additional memory.
- Uses
#![no_std]
.
Examples
let mut v = [-5i32, 4, 1, -3, 2];
let k = 3;
pdqselect::select(&mut v, k);
let kth = v[k];
assert!(v[..k].iter().all(|&x| x <= kth));
assert!(v[k+1..].iter().all(|&x| x >= kth));
pdqselect::select_by(&mut v, k, |a, b| b.cmp(a));
let kth = v[k];
assert!(v[..k].iter().all(|&x| x >= kth));
assert!(v[k+1..].iter().all(|&x| x <= kth));
pdqselect::select_by_key(&mut v, k, |k| k.abs());
let kth = v[k].abs();
assert!(v[..k].iter().all(|&x| x.abs() <= kth));
assert!(v[k+1..].iter().all(|&x| x.abs() >= kth));