adqselect

A lightweight, zero-dependency crate that provides an efficient nth_element implementation in Rust based on Andrei Alexandrescu’s Adaptive Quickselect algorithm.
Available on crates.io.

Installation

Add the crate to your Cargo.toml:

[dependencies]
adqselect = "0.1.5"

Usage

use adqselect::nth_element;

fn main() {
    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);
}

nth_element rearranges the vector so that the element at position n is the same as if the vector were fully sorted but runs in O(n) time on average.

The elements before index n are less than or equal to v[n], and those after are greater than or equal.

Implementation

Based on the paper

Fast Deterministic Selection (Andrei Alexandrescu, 2016)

This algorithm refines the classic Median of Medians approach to achieve strong performance guarantees while remaining practical.

Performance

adqselect guarantees linear deterministic time complexity and is competitive with popular selection crates such as:

• floydrivest
• order-stat
• kth
• pdqselect

Benchmarks

Detailed benchmarks are available in the repository, comparing throughput and allocation efficiency across datasets of varying size and distribution.

License

Licensed under the MIT License.