sort Example, Strings (Ordering)
This page was last reviewed on Apr 4, 2023.
Dot Net Perls
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
An example. 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 sort_by and sort_unstable_by functions can be used. The unstable version is faster, but may move equal elements more.
Note 2 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
A discussion. In many Rust programs, using the "unstable" functions is acceptable, as the order of equal elements does not matter. There is a performance benefit to "unstable" too.
Also For reverse sorts, just change the order of the comparisons (when calling the cmp function).
A summary. 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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Apr 4, 2023 (new example).
© 2007-2024 Sam Allen.