Step 3 of 7

Sorting and custom orderings

You've used sort since the vectors module. Here's what's behind it, and how to sort by anything.

• v.sort() is stable: items that compare equal keep their original order. It's O(n log n) and uses some extra memory.
• v.sort_unstable() may reorder equal items, but it's usually faster and needs no extra memory. For plain numbers, where equal items are indistinguishable, it's the idiomatic choice (clippy's pedantic stable_sort_primitive lint suggests it).
• Both need T: Ord. For anything else, say how to compare:

Several keys

cmp returns an Ordering (Less, Equal or Greater). ordering.then(other) uses other only when the first comparison was Equal, which is exactly how "sort by department, then by salary" works. then_with(|| ...) does the same but only computes the second comparison when needed. To flip one key, swap a and b (or call .reverse() on that Ordering).

use std::cmp::Reverse;

struct Employee {
    name: &'static str,
    dept: &'static str,
    salary: u32,
}

fn main() {
    let mut staff = vec![
        Employee { name: "Mo", dept: "ops", salary: 61_000 },
        Employee { name: "Ana", dept: "dev", salary: 82_000 },
        Employee { name: "Bo", dept: "dev", salary: 95_000 },
        Employee { name: "Cy", dept: "ops", salary: 61_000 },
        Employee { name: "Di", dept: "dev", salary: 82_000 },
    ];
    // department A-Z, then salary high to low, then name A-Z
    staff.sort_by(|a, b| {
        a.dept
            .cmp(&b.dept)
            .then(b.salary.cmp(&a.salary))
            .then(a.name.cmp(&b.name))
    });
    for e in &staff {
        println!("{:<4} {:<4} {}", e.dept, e.name, e.salary);
    }

    staff.sort_by_key(|e| Reverse(e.salary));
    println!("top earner: {}", staff[0].name);

    let mut temps: Vec<f64> = vec![21.5, -3.0, 18.25, 0.0];
    temps.sort_by(|a, b| a.total_cmp(b));
    println!("{temps:?}");
}

dev  Bo   95000
dev  Ana  82000
dev  Di   82000
ops  Cy   61000
ops  Mo   61000
top earner: Bo
[-3.0, 0.0, 18.25, 21.5]

• Floats don't implement Ord (NaN isn't comparable), so sort won't compile on a Vec<f64>. f64::total_cmp is a full ordering for floats, made for exactly this. (The : Vec<f64> annotation matters: total_cmp belongs to a specific float type, and a bare 21.5 could still be an f32.)
• When a type has one obvious order (a version number, a date), implement Ord for it (module 23) and plain sort() works. When the order depends on the screen or report, use sort_by.
• Related tools: v.is_sorted(), iter.max_by_key(...), iter.min_by(|a, b| a.total_cmp(b)).

Common mistakes

• Sorting floats with sort():

fn main() {
    let mut v = vec![3.2, 1.5, 2.0];
    v.sort();
    println!("{:?}", v);
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied

• sort_by_key with a String field. The key closure must return the key by value, and it can't move the String out of the borrowed item:

struct Player {
    name: String,
    score: u32,
}

fn main() {
    let mut players = vec![Player { name: String::from("Zed"), score: 3 }];
    players.sort_by_key(|p| p.name);
    println!("{}", players[0].score);
}

error[E0507]: cannot move out of `p.name` which is behind a shared reference

Use sort_by(|a, b| a.name.cmp(&b.name)) (no copy) rather than sort_by_key(|p| p.name.clone()) (a new String for every comparison).

• Descending with a minus sign. sort_by_key(|x| -x) doesn't work for unsigned types and overflows for i32::MIN. Use Reverse(x).
• No tie-breaker. If two items can compare equal, decide what happens; otherwise the output order depends on the input order, and tests break when the input changes.

Your task

Write fn rank_players(players: &mut [Player]) that sorts a leaderboard: highest score first; on equal scores, fewer games first; on equal games too, name A to Z.

Challenge 2

A sensor dashboard shows the median temperature: the middle value once the readings are sorted, or the average of the two middle values when there's an even number of them. The median is popular in monitoring because a single crazy reading can't drag it around the way it drags the average.

Write fn median(readings: &[f64]) -> Option<f64> (None for no readings). Sort a copy with total_cmp; don't change the caller's slice.

Challenge 3

HR exports the staff list as CSV and wants it grouped for the salary review. Standard input starts with a header line name,dept,salary, followed by one employee per line, like Ana,dev,82000. Skip the header and blank lines.

Print each department (A to Z) on its own line, followed by its employees from the highest salary to the lowest (equal salaries: name A to Z), each printed with println!(" {:<8}{:>6}", name, salary):

dev
  Bo       95000
  Ana      82000
ops
  Cy       61000

Previous: Linear and binary search Next: Implementing sorts: insertion sort and merge sort