# Crate pdqselect [−] [src]

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 `sort_unstable`

.

# 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

heapsort |
Sorts |

select |
Partially sorts a slice and puts the |

select_by |
Partially sorts a slice using |

select_by_key |
Partially sorts a slice using |