Learn/Rust/12. Sorting and searching
Lesson 12 of 15
Sign in

Rust, lesson 12

Sorting and searching

Sorting is built into Rust's slices, so every Vec can sort itself in place. Once data is sorted, binary search finds items in a handful of steps.

Simple sorting

sort changes the vector in place, so it must be mut. It is stable: equal elements keep their original order. sort_unstable is a little faster and does not promise that. Strings sort by their bytes, so uppercase letters come before lowercase ones.

Floats cannot use sort directly, because NaN has no place in an order. Sort them with v.sort_by(|a, b| a.total_cmp(b)).

Custom orders

sort_by takes a closure that compares two elements and returns an : , or . Every comparable type has a method that returns one:

2 exercises to try what you just read.

Exercise 1

Leaderboard

Press Ctrl Enter or Check to test your code.

Exercise 2

Price check

Press Ctrl Enter or Check to test your code.

Ordering
Less
Equal
Greater
cmp

sort_by_key is shorter when you sort by one value pulled from each element:

For descending order with sort_by_key, wrap the key in std::cmp::Reverse: runners.sort_by_key(|r| Reverse(r.time)).

Breaking ties

Ordering has a then method (and then_with, which takes a closure): if the first comparison says Equal, the second one decides.

Tuples compare element by element, so a key like (Reverse(score), name.clone()) sorts by score descending, then name ascending. For keys that borrow from the element, use sort_by instead of sort_by_key.

Linear and binary search

v.contains(&x) and v.iter().position(|y| *y == x) look at elements one by one. That is fine for small lists but slow for large ones.

On a sorted slice, binary_search halves the search range at each step, so a million items take about 20 comparisons. It returns a Result:

The Err value is the insertion point: the index where the value would go to keep the slice sorted. That also equals the number of elements smaller than the target (when the elements are distinct), which answers questions like "how many prices are cheaper than this?".

binary_search_by and binary_search_by_key work like the sort_by versions. Searching only makes sense if the slice is sorted by the same key; otherwise the result is meaningless.

partition_point(|x| *x < target) is a handy alternative: it returns the index of the first element for which the condition is false.

Further reading

  • Primitive type slice: sort, sort_by, binary_search
  • std::cmp::Ordering
  • std::cmp::Reverse

The first line holds n, the number of players. Each of the next n lines holds a name and a score. Print the leaderboard: highest score first; equal scores in alphabetical order of name. Number the lines from 1, as <rank>. <name> <score>.

Sample input:

Sample output:

A shop has a sorted price list. The first line holds n, the next line n prices in ascending order (it may be empty when n is 0). Then a line with q, and a line with q query prices. For each query p, print p: found at <index> if it is in the list (indexes start at 0), otherwise p: <k> cheaper, where k is how many listed prices are below p. Use binary_search.

Sample input:

Sample output:

let mut nums = vec![42, 7, 19];
nums.sort();
println!("{nums:?}"); // [7, 19, 42]

let mut names = vec!["pear", "Apple", "fig"];
names.sort();
println!("{names:?}"); // ["Apple", "fig", "pear"]
struct Runner {
    name: String,
    time: u32,
}

runners.sort_by(|a, b| a.time.cmp(&b.time));   // fastest first
runners.sort_by(|a, b| b.time.cmp(&a.time));   // slowest first (swapped)
runners.sort_by_key(|r| r.time);
runners.sort_by(|a, b| a.time.cmp(&b.time).then(a.name.cmp(&b.name)));
let sorted = [3, 8, 15, 23, 42];
assert_eq!(sorted.binary_search(&23), Ok(3));  // found at index 3
assert_eq!(sorted.binary_search(&10), Err(2)); // not found; would go at index 2
4
zed 50
amy 80
bob 50
cat 95
1. cat 95
2. amy 80
3. bob 50
4. zed 50
5
3 8 15 23 42
3
23 10 50
23: found at 3
10: 2 cheaper
50: 5 cheaper