Сортировка и поиск в Rust

Сортировка и поиск встречаются почти в каждой программе: рейтинг игроков по очкам, список файлов по имени, поиск самого дешёвого товара. У векторов и срезов в Rust есть набор встроенных методов и для того, и для другого, так что писать свой алгоритм приходится редко.

Большинство этих методов принимают замыкание, которое говорит, как сравнивать два элемента. Когда эта идея станет привычной, всё остальное на странице — лишь её вариации.

Строки в примерах этой страницы оставлены на английском: результат сортировки зависит от букв, и так он совпадает с тем, что ты увидишь в Playground.

sort и sort_unstable

.sort() расставляет элементы по возрастанию (сначала самые маленькие). Он меняет вектор на месте, поэтому вектор должен быть mut. Числа сортируются по значению, строки — по алфавиту.

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

Вывод:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ Попробуй сам

Обрати внимание на две вещи:

"adam" оказался последним. Строки сравниваются по кодам символов, а любая заглавная буква идёт раньше любой строчной. Если нужен «словарный» порядок, сортируй по name.to_lowercase() (это показано ниже).
sort_unstable обычно чуть быстрее и не использует дополнительную память. «Нестабильная» (unstable) не значит «с ошибками». Это значит, что элементы, которые при сравнении равны, могут поменяться местами. Для обычных чисел и строк разницы не увидеть, так что это хороший выбор по умолчанию.

Обратный порядок

Есть три распространённых способа отсортировать от большего к меньшему. Здесь все они дают одинаковый результат.

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // y раньше x = по убыванию
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

Вывод:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ Попробуй сам

x.cmp(y) возвращает Ordering: Less, Equal или Greater. По нему sort_by решает, какой элемент поставить первым. Если написать y.cmp(x), каждое решение переворачивается, а вместе с ним и весь порядок. Reverse — маленькая обёртка из std::cmp, которая делает тот же переворот для ключа.

Сортировка дробных чисел

Попробуй вызвать .sort() у вектора f64 — и Rust откажется:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

Компилятор сообщает, что для дробных чисел не реализован трейт Ord. Почему? .sort() нужен полный порядок (трейт Ord): из любых двух значений одно должно быть меньше, равно или больше другого. А у дробных чисел есть особое значение NaN («не число»), которое не меньше, не равно и не больше ничего — даже самого себя. Поэтому у дробных чисел есть только PartialOrd, а .partial_cmp() возвращает Option<Ordering>, который для NaN равен None.

Есть два хороших способа это исправить:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // Если ты уверен, что NaN нет:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Работает даже с NaN (NaN уходит в конец):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Вывод:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ Попробуй сам

partial_cmp(...).unwrap() вызовет панику, если встретит NaN. total_cmp не паникует никогда, потому что задаёт фиксированное место для каждого дробного числа, включая NaN. Если нет особых причин, выбирай total_cmp.

sort_by_key и сортировка структур

sort_by_key принимает замыкание, которое выбирает, по чему сортировать. Это идеально подходит для структур: ты выбираешь поле.

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

Вывод:

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ Попробуй сам

Замыкание-ключ должно возвращать значение, которым оно владеет. p.price_cents — это u32, он копируется, так что всё в порядке. Для поля String нужна новая String — поэтому вторая сортировка использует to_lowercase(), который её создаёт. (Подробнее — в разделе об ошибках ниже.)

Сортировка по нескольким полям

Классическая задача: отсортировать учеников по оценке, сначала самые высокие, а при одинаковой оценке — по имени от A до Z. Используй sort_by с .then_with(). Второе сравнение выполняется, только когда первое дало ничью.

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // оценка: от высокой к низкой
            .then_with(|| a.name.cmp(&b.name)) // потом имя: от A до Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

Вывод:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Попробуй сам

Покороче — вернуть в качестве ключа кортеж. Кортежи сравнивают первый элемент, потом второй и так далее:

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

Порядок получается точно такой же. Запись аккуратная, но она клонирует каждое имя, поэтому для больших списков лучше привыкнуть к sort_by с then_with.

Убираем повторы через dedup

.dedup() удаляет элементы, которые равны элементу прямо перед ними. Поэтому все повторы он уберёт, только если список сначала отсортирован.

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("только dedup: {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup: {:?}", tags);
}

Вывод:

только dedup: ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ Попробуй сам

В первой попытке слились только два "web", которые стояли рядом. Сначала сортируй, потом dedup. Если нужно сохранить исходный порядок, используй приём с HashSet из урока HashSet и BTreeMap.

Поиск: contains, position, max, min, binary_search

Вот инструменты поиска, которые нужны чаще всего:

contains(&x) — есть ли такой элемент? Возвращает bool.
iter().position(...) — где первое совпадение? Возвращает Option<usize>.
iter().max() / iter().min() — наибольший и наименьший элементы в виде Option (для пустого списка — None).
iter().max_by_key(...) / min_by_key(...) — наибольший или наименьший по какому-то полю.
binary_search(&x) — очень быстрый поиск, но только в отсортированном списке. Возвращает Ok(индекс), если нашёл, или Err(индекс) — где элемент должен был бы стоять.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("есть 31? {}", temps.contains(&31));
    println!("первое больше 20 на позиции: {:?}", temps.iter().position(|&t| t > 20));
    println!("максимум: {:?}, минимум: {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("лучший игрок: {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // список остаётся отсортированным
    }
    println!("{:?}", sorted);
}

Вывод:

есть 31? true
первое больше 20 на позиции: Some(1)
максимум: Some(31), минимум: Some(12)
лучший игрок: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Попробуй сам

binary_search (двоичный поиск) смотрит на средний элемент, отбрасывает половину, в которой значения быть не может, и повторяет. В списке из миллиона элементов это около 20 проверок вместо миллиона. Ответ Err(pos) тоже полезен: если вставить элемент на позицию pos, список останется отсортированным.

Частые ошибки

Вернуть заимствованное поле String из sort_by_key. Выглядит естественно, но не компилируется:

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

Компилятор говорит, что нельзя переместить s.name, потому что оно находится за общей (неизменяемой) ссылкой. Замыкание только заимствует каждого ученика, поэтому не может отдать String. Либо клонируй её (|s| s.name.clone()), либо обойдись совсем без копии: sort_by(|a, b| a.name.cmp(&b.name)).

Использовать binary_search на неотсортированном списке. Программа не упадёт, но ответ будет бессмысленным: поиск может сказать, что значения нет, хотя оно прямо там. Всегда сначала сортируй или используй contains / position.

Практика

1. Таблица лидеров

Игроки заданы кортежами (имя, очки): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Отсортируй их по очкам, начиная с наибольших, а при равенстве — по имени от A до Z. Выведи только первую тройку. Подсказка: используй sort_by с .then_with(), а для первой тройки — срез &players[..3].

Показать решение

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

Вывод:

95 ana
88 dev
70 ben

▶ Попробуй сам

В кортеже .0 — это имя, а .1 — очки. У ben и chen по 70, поэтому ничью разрешает имя, и в тройку попадает ben.

2. Медианная цена

Найди медиану (среднее по положению значение) цен 3.5, 1.25, 9.0, 4.75, 2.0. Выведи отсортированный список и медиану. Подсказка: отсортируй через total_cmp; средний элемент списка нечётной длины стоит на индексе len() / 2.

Показать решение

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("по порядку: {:?}", prices);
    println!("медиана: {median}");
}

Вывод:

по порядку: [1.25, 2.0, 3.5, 4.75, 9.0]
медиана: 3.5

▶ Попробуй сам

Аннотация типа Vec<f64> здесь важна. Без неё к моменту вызова total_cmp Rust ещё не знает, какого именно дробного типа числа, и отказывается компилировать с ошибкой «no method named total_cmp» («нет метода с именем total_cmp»).

Итоги

sort() и sort_unstable() сортируют на месте, начиная с меньшего. Для обратного порядка — reverse(), y.cmp(x) или Reverse.
Дробные числа не сортируются через sort() из-за NaN. Используй sort_by(|a, b| a.total_cmp(b)).
sort_by_key сортирует по выбранному полю; sort_by с .then_with() — по нескольким полям.
dedup() удаляет только равных соседей, поэтому сначала сортируй.
contains, position, max/min и max_by_key ищут в любом списке; binary_search гораздо быстрее, но требует отсортированного списка.

Проверь себя

1. Почему vec![1.5, 0.5].sort() не компилируется?

2. Что останется в векторе после vec![1, 1, 2, 1].dedup()?

3. Что вернёт vec![10, 20, 30].binary_search(&25)?

4. Когда в a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)) сравниваются имена?

Результат: 0 / 4

Что почитать

Slice methods: sort, sort_by, binary_search and more — документация стандартной библиотеки (на английском): все методы сортировки и поиска с заметками о скорости и стабильности.
std::cmp::Ordering — документация стандартной библиотеки (на английском): Less, Equal, Greater, а ещё then, then_with и reverse.
std::cmp::Reverse — документация стандартной библиотеки (на английском): обёртка для сортировки по ключу от большего к меньшему.
f64::total_cmp — документация стандартной библиотеки (на английском): куда именно попадают NaN, отрицательный ноль и бесконечность при сортировке дробных чисел.
Sort a Vector — Rust Cookbook (на английском): короткие рецепты сортировки целых чисел, дробных чисел и структур.