#quick-sort #select #nth-element #quickselect #pdqsort

no-std pdqselect

Selects the kth smallest element of a slice, based on Orson Peters's Pattern Defeating Quickselect

2 releases

0.1.1 Nov 15, 2021
0.1.0 Oct 20, 2017

#505 in Algorithms

Download history 2884/week @ 2024-07-22 2620/week @ 2024-07-29 2476/week @ 2024-08-05 3383/week @ 2024-08-12 2534/week @ 2024-08-19 2707/week @ 2024-08-26 2922/week @ 2024-09-02 2201/week @ 2024-09-09 2100/week @ 2024-09-16 3006/week @ 2024-09-23 2457/week @ 2024-09-30 1702/week @ 2024-10-07 2498/week @ 2024-10-14 2472/week @ 2024-10-21 3719/week @ 2024-10-28 22077/week @ 2024-11-04

30,813 downloads per month
Used in 121 crates (9 directly)

Apache-2.0/MIT

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

No runtime deps