Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to sort a Vector in descending order in Rust?

Tags:

sorting

rust

In Rust, the sorting methods of a Vec always arrange the elements from smallest to largest. What is a general-purpose way of sorting from largest to smallest instead?

If you have a vector of numbers, you can provide a key extraction function that "inverts" the number like this:

let mut numbers: Vec<u32> = vec![100_000, 3, 6, 2];
numbers.sort_by_key(|n| std::u32::MAX - n);

But that's not very clear, and it's not straightforward to extend that method to other types like strings.

like image 526
nnnmmm Avatar asked Mar 29 '20 15:03

nnnmmm


People also ask

How do you sort a vector in Rust?

To sort a vector v , in most cases v. sort() will be what you need. If you want to apply a custom ordering rule, you can do that via v. sort_by() .

How do you order a vector in descending order?

Sorting a vector in descending order in C++ Sorting a vector in C++ can be done by using std::sort(). It is defined in<algorithm> header. To get a stable sort std::stable_sort is used. It is exactly like sort() but maintain the relative order of equal elements.

How do you sort a vector in ascending and descending order r?

To sort a vector in R programming, call sort() function and pass the vector as argument to this function. sort() function returns the sorted vector in increasing order. The default sorting order is increasing order. We may sort in decreasing order using rev() function on the output returned by sort().

How do you sort a vector in descending order in Python?

Sort NumPy Array in decreasing order using sort() arranges all the elements in increasing order. In order to sort a NumPy Array in descending order, we will pass the given array to the sort() method and it will return the sorted array in ascending order. Then we will reverse the array using slicing.


1 Answers

There are at least three ways to do it.

Flipped comparison function

vec.sort_by(|a, b| b.cmp(a))

This switches around the order in which elements are compared, so that smaller elements appear larger to the sorting function and vice versa.

Wrapper with reverse Ord instance

use std::cmp::Reverse;
vec.sort_by_key(|w| Reverse(*w));

Reverse is a generic wrapper which has an Ord instance that is the opposite of the wrapped type's ordering.

If you try to return a Reverse containing a reference by removing the *, that results in a lifetime problem, same as when you return a reference directly inside sort_by_key (see also this question). Hence, this code snippet can only be used with vectors where the keys are Copy types.

Sorting then reversing

vec.sort();
vec.reverse();

It initially sorts in the wrong order and then reverses all elements.

Performance

I benchmarked the three methods with criterion for a length 100_000 Vec<u64>. The timing results are listed in the order above. The left and right values show the lower and upper bounds of the confidence interval respectively, and the middle value is criterion's best estimate.

Performance is comparable, although the flipped comparison function seems to be a tiny bit slower:

Sorting/sort_1          time:   [6.2189 ms 6.2539 ms 6.2936 ms]
Sorting/sort_2          time:   [6.1828 ms 6.1848 ms 6.1870 ms]
Sorting/sort_3          time:   [6.2090 ms 6.2112 ms 6.2138 ms]

To reproduce, save the following files as benches/sort.rs and Cargo.toml, then run cargo bench. There is an additional benchmark in there which checks that the cost of cloning the vector is irrelevant compared to the sorting, it only takes a few microseconds.

fn generate_shuffled_data() -> Vec<u64> {
    use rand::Rng;
    let mut rng = rand::thread_rng();
    (0..100000).map(|_| rng.gen::<u64>()).collect()
}

pub fn no_sort<T: Ord>(vec: Vec<T>) -> Vec<T> {
    vec
}

pub fn sort_1<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort_by(|a, b| b.cmp(a));
    vec
}

pub fn sort_2<T: Ord + Copy>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort_by_key(|&w| std::cmp::Reverse(w));
    vec
}

pub fn sort_3<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
    vec.sort();
    vec.reverse();
    vec
}

use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn comparison_benchmark(c: &mut Criterion) {
    let mut group = c.benchmark_group("Sorting");
    let data = generate_shuffled_data();

    group.bench_function("no_sort", |b| {
        b.iter(|| black_box(no_sort(data.clone())))
    });

    group.bench_function("sort_1", |b| {
        b.iter(|| black_box(sort_1(data.clone())))
    });

    group.bench_function("sort_2", |b| {
        b.iter(|| black_box(sort_2(data.clone())))
    });

    group.bench_function("sort_3", |b| {
        b.iter(|| black_box(sort_3(data.clone())))
    });

    group.finish()
}

criterion_group!(benches, comparison_benchmark);
criterion_main!(benches);
[package]
name = "sorting_bench"
version = "0.1.0"
authors = ["nnnmmm"]
edition = "2018"

[[bench]]
name = "sort"
harness = false

[dev-dependencies]
criterion = "0.3"
rand = "0.7.3"
like image 148
nnnmmm Avatar answered Oct 28 '22 01:10

nnnmmm