Rust, lesson 12
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.
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)).
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.
OrderingLessEqualGreatercmpsort_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)).
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.
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.
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 24
zed 50
amy 80
bob 50
cat 951. cat 95
2. amy 80
3. bob 50
4. zed 505
3 8 15 23 42
3
23 10 5023: found at 3
10: 2 cheaper
50: 5 cheaper