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.
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() .
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.
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().
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.
There are at least three ways to do it.
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.
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.
vec.sort();
vec.reverse();
It initially sorts in the wrong order and then reverses all elements.
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"
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With