### 4 releases

0.1.3 | Jan 10, 2021 |
---|---|

0.1.2 | Jan 10, 2021 |

0.1.1 | Aug 13, 2020 |

0.1.0 | Aug 13, 2020 |

#**147** in Algorithms

**MIT**license

**1.5MB**

339 lines

# adqselect

A lightweight crate that brings to Rust an

implementation that leverages Andrei Alexandrescu's `nth_element`**adaptive quickselect** algorithm. Also available on crates.io.

## Installation

Be sure that your

looks somewhat like this:`Cargo .toml`

`[``dependencies``]`
`adqselect ``=` `"`0.1.3`"`

## Usage

Bring the crate into scope:

`extern` `crate` adqselect`;`
`use` `adqselect``::`nth_element`;`

then simply call

on a vector.`nth_element`

`let` `mut` v `=` `vec!``[``10``,` `7``,` `9``,` `7``,` `2``,` `8``,` `8``,` `1``,` `9``,` `4``]``;`
`nth_element``(``&``mut` v`,` `3``,` `&``mut` `Ord``::`cmp`)``;`
`assert_eq!``(`v`[``3``]``,` `7``)``;`

This implementation also handles generic data types as long as they satisfy the

and `PartialEq`

traits.`PartialOrd`

## Implementation

Link to the original paper: Fast Deterministic Selection by Andrei Alexandrescu.

## Performance

The algorithm is based on a refined version of Median of Medians and it guarantees linear deterministic time complexity.

## Benchmarks

Here are some benchmarks against other crates: floydrivest, order-stat, kth and pdqselect.

## Results

### Violin Plot

This chart shows the relationship between function/parameter and iteration time. The thickness of the shaded region indicates the probability that a measurement of the given function/parameter would take a particular length of time.

### Line Chart

This chart shows the mean measured time for each function as the input (or the size of the input) increases.

#### adqselect on 1.000 random unsigned integers

#### adqselect on 10.000 random unsigned integers

#### adqselect on 100.000 random unsigned integers

#### adqselect on 1.000.000 random unsigned integers

#### floydrivest on 1.000 random unsigned integers

#### floydrivest on 10.000 random unsigned integers

#### floydrivest on 100.000 random unsigned integers

#### floydrivest on 1.000.000 random unsigned integers

#### kth on 1.000 random unsigned integers

#### kth on 10.000 random unsigned integers

#### kth on 100.000 random unsigned integers

#### kth on 1.000.000 random unsigned integers

#### order_stat on 1.000 random unsigned integers

#### order_stat on 10.000 random unsigned integers

#### order_stat on 100.000 random unsigned integers

#### order_stat on 1.000.000 random unsigned integers

#### pdqselect on 1.000 random unsigned integers

#### pdqselect on 10.000 random unsigned integers

#### pdqselect on 100.000 random unsigned integers

#### pdqselect on 1.000.000 random unsigned integers

This report was generated by Criterion.rs, a statistics-driven benchmarking library in Rust.