# Crate pdqselect[−][src]

Expand description

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

## Functions

Sorts `v` using heapsort, which guarantees `O(n log n)` worst-case.

Partially sorts a slice and puts the `k`th smallest item in place.

Partially sorts a slice using `compare` to compare elements and puts the `k`th smallest item in place.

Partially sorts a slice using `f` to extract a key to compare elements by and puts the `k`th smallest item in place.