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

**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 `=` `[``-``5``i32``,` `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`)``)``;`