Rust - sort Example, Strings (Ordering)

Sort. Sorting a vector of Strings in Rust can be done with a single function call. But more complex sorting, like with 2 properties at once, requires a custom function.

By returning Ordering, we can use a custom function with the sort_by and sort_unstable_by functions. In this way we can implement more complex, compound sorting routines.

Sort HashMap

Sort Alphanumeric

To begin, we need to add a "use" statement at the top of the program for "cmp" to access Ordering. In main, we add 5 Strings to a vector.

Tip In main, we call to_string() to get Strings, not str references. With String, we can avoid ownership issues and Rust programs are simpler.

String Array

Note The first function is compare_len_reverse_alpha. This has 2 calls to cmp() in it.

Info In "compare" we test the lengths of the 2 string arguments first. If the lengths are equal, we sort them in reverse alphabetical order.

String Length

use std::cmp::*; fn compare_len_reverse_alpha(a: &String, b: &String) -> Ordering { // Sort by length from short to long first. let length_test = a.len().cmp(&b.len()); if length_test == Ordering::Equal { // If same length, sort in reverse alphabetical order. return b.cmp(&a); } return length_test; } fn main() { // The vec we want to sort. let mut animals = vec![]; animals.push("bird".to_string()); animals.push("elephant".to_string()); animals.push("cat".to_string()); animals.push("ant".to_string()); animals.push("bat".to_string()); // Call the function that returns Ordering. animals.sort_unstable_by(compare_len_reverse_alpha); // Print results. println!("{:?}", animals); }

["cat", "bat", "ant", "bird", "elephant"]

Sort by key. Sometimes we want to sort a vector by only part of each element (like a key). This can be done with the sort_by_key function.

fn main() { let mut items = vec![(10, 1), (0, 2), (30, 0)]; // Sort by the second value in each tuple. items.sort_by_key(|x| x.1); println!("{:?}", items); }

[(30, 0), (10, 1), (0, 2)]

Cached key. If we want to sort a collection in a more complex way, it can take some time to compute each key. With sort_by_cached_key, we avoid computing this information more than once.

Tip The sort_by_cached_key function can speed up sorting some collections in a significant way. Always test to make sure.

Here We sort the str references by the number of lowercase letter "w" values in them, from low to high.

fn count_letter(value: &str, letter: char) -> usize { value.chars().filter(|&x| x == letter).count() } fn main() { let mut words = vec!["window", "work", "cat"]; // Sort by count of letter "w" from low to high. words.sort_by_cached_key(|x| count_letter(x, 'w')); println!("{:?}", words); }

["cat", "work", "window"]

Cached keys benchmark. When can using sort_by_cached_key improve performance over just calling sort_by_key? Usually if some sort of allocation occurs, cached keys help.

Version 1 This version of the code uses sort_by_cached_key, so it only performs the uppercasing operation once per key.

Version 2 Here we call sort_by_key, which may uppercase the strings multiple times per call.

Result With this key selection function (uppercase_count_letter), it is faster to invoke sort_by_cached_key.

use std::time::*; fn uppercase_count_letter(value: &str, letter: char) -> usize { value .to_ascii_uppercase() .chars() .filter(|&x| x == letter) .count() } fn main() { let mut words = vec!["window", "work", "cat", "www"]; if let Ok(max) = "10000000".parse::<usize>() { // Version 1: use cached keys. let t0 = Instant::now(); for _ in 0..max { words.sort_by_cached_key(|x| uppercase_count_letter(x, 'W')); } println!("{} ms", t0.elapsed().as_millis()); // Version 2: use keys. let t1 = Instant::now(); for _ in 0..max { words.sort_by_key(|x| uppercase_count_letter(x, 'W')); } println!("{} ms", t1.elapsed().as_millis()); } }

1696 ms 2215 ms

Sort_unstable. This benchmark aims to determine how much performance we can gain from using sort_unstable. It uses a small array of only 8 elements.

Version 1 The first version of the loop uses sort() on a copy of the original array. The loop iterates many times.

Version 2 This version is the same as the first version, but it uses sort_unstable instead of sort.

Result Even on an unsorted array of 8 integers, the sort_unstable method seems to be reliably faster.

use std::time::Instant; fn main() { let items_original = [10, 20, 5, -10, 100, 200, -200, 0]; if let Ok(max) = "100000000".parse::<usize>() { // Version 1: use sort. let t0 = Instant::now(); for i in 0..max { let mut items = items_original; items.sort(); if items[0] != -200 { break; } } println!("{:?}", t0.elapsed()); // Version 2: use sort_unstable. let t1 = Instant::now(); for i in 0..max { let mut items = items_original; items.sort_unstable(); if items[0] != -200 { break; } } println!("{:?}", t1.elapsed()); } }

500.9585 ms sort 476.249709ms sort_unstable

We implemented a compound sort on a string vector in Rust. Often we need to sort by one aspect, and then by another—a custom Ordering function is needed for this.