Ordenação e busca em Rust

Ordenar e buscar são duas tarefas que você vai fazer em quase todo programa: classificar jogadores pela pontuação, listar arquivos pelo nome, achar o produto mais barato. O Rust dá aos vetores e aos slices um conjunto de métodos prontos para as duas coisas, então você raramente precisa escrever seu próprio algoritmo.

A maioria desses métodos recebe uma closure (função anônima) que diz como comparar dois itens. Quando você pegar o jeito dessa ideia, o resto da página é só variação em cima dela.

sort e sort_unstable

.sort() coloca os itens em ordem crescente (o menor primeiro). Ele altera o vetor no lugar, então o vetor precisa ser mut. Números são ordenados pelo valor; strings, em ordem alfabética.

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);
}

Saída:

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

▶ Experimente você mesmo

Duas coisas para notar:

• "adam" fica por último. Strings são comparadas pelo código de cada caractere, e toda letra maiúscula vem antes de qualquer minúscula. Ordene por name.to_lowercase() (mostrado mais abaixo) se quiser a ordem “de dicionário”.
• sort_unstable costuma ser um pouco mais rápido e não usa memória extra. “Instável” não quer dizer que tem bug. Quer dizer que itens considerados iguais na comparação podem trocar de lugar entre si. Com números ou strings simples não dá para notar a diferença, então ele é uma ótima escolha padrão.

Os nomes e as palavras dos exemplos desta página ficaram em inglês porque a saída mostra a ordem deles, e com outras palavras a ordem mudaria.

Ordem decrescente

Há três jeitos comuns de ordenar do maior para o menor. Aqui, todos dão o mesmo resultado.

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 antes de x = decrescente
    println!("{:?}", b);

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

Saída:

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

▶ Experimente você mesmo

x.cmp(y) devolve um Ordering: Less (menor), Equal (igual) ou Greater (maior). O sort_by usa isso para decidir qual item vem primeiro. Escrever y.cmp(x) inverte cada decisão, e com isso inverte a ordem inteira. Reverse é um pequeno invólucro de std::cmp que faz a mesma inversão para uma chave.

Ordenando floats

Tente usar .sort() em um vetor de f64 e o Rust recusa:

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}`

O compilador está dizendo que os números de ponto flutuante não implementam o trait Ord. Por quê? .sort() precisa de uma ordem total (o trait Ord): para quaisquer dois valores, um tem que ser menor, igual ou maior que o outro. Os floats têm um valor especial, NaN (“not a number”, não é um número), que não é menor, igual nem maior que nada, nem que ele mesmo. Por isso os floats só têm PartialOrd, e .partial_cmp() devolve um Option<Ordering> que é None para NaN.

Você tem duas boas soluções:

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

    // Se você tem certeza de que não há NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Funciona mesmo com NaN (o NaN vai para o fim):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Saída:

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

▶ Experimente você mesmo

partial_cmp(...).unwrap() vai dar panic se encontrar um NaN. total_cmp nunca dá panic, porque define um lugar fixo para cada float, inclusive o NaN. Prefira total_cmp, a menos que tenha um motivo para não usar.

sort_by_key e ordenação de structs

sort_by_key recebe uma closure que escolhe pelo que ordenar. Isso é perfeito para structs, em que você escolhe um campo.

#[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);
}

Saída:

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

▶ Experimente você mesmo

Os produtos são uma caneta (“pen”), um caderno (“Notebook”) e uma borracha (“eraser”). A closure da chave precisa devolver um valor próprio (owned). p.price_cents é um u32, que é copiado, então tudo bem. Para um campo String, você precisa de uma String nova. É por isso que a segunda ordenação usa to_lowercase(), que cria uma. (Veja a seção de erros comuns mais abaixo.)

Ordenando por vários campos

Uma tarefa clássica: ordenar alunos pela nota, da maior para a menor, e, quando dois alunos tiverem a mesma nota, ordená-los pelo nome de A a Z. Use sort_by com .then_with(). Ele só olha a segunda comparação quando a primeira dá empate.

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)               // nota: da maior para a menor
            .then_with(|| a.name.cmp(&b.name)) // depois o nome: de A a Z
    });

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

Saída:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Experimente você mesmo

Uma alternativa mais curta é devolver uma tupla como chave. Tuplas comparam o primeiro item, depois o segundo, e assim por diante:

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

Isso dá exatamente a mesma ordem. Fica enxuto, mas clona todos os nomes, então sort_by com then_with é o melhor hábito para listas grandes.

Removendo repetidos com dedup

.dedup() remove os itens iguais ao que está logo antes deles. Por isso, ele só remove todos os repetidos se a lista estiver ordenada antes.

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

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("dedup only:   {:?}", not_sorted);

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

Saída:

dedup only:   ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ Experimente você mesmo

Os rótulos ficaram em inglês porque estão alinhados com espaços: “dedup only” quer dizer “só dedup”. Na primeira tentativa, só os dois "web" que estavam lado a lado foram juntados. Ordene primeiro e depois use dedup. Se precisar manter a ordem original, use o truque com HashSet da página de HashSet.

Buscando: contains, position, max, min, binary_search

Estas são as ferramentas de busca que você mais vai usar:

• contains(&x): está lá? Devolve bool.
• iter().position(...): onde está a primeira ocorrência? Devolve Option<usize>.
• iter().max() / iter().min(): o maior e o menor, como um Option (é None para uma lista vazia).
• iter().max_by_key(...) / min_by_key(...): o maior ou o menor de acordo com algum campo.
• binary_search(&x): busca muito rápida, mas só em uma lista ordenada. Devolve Ok(index) se encontrar, ou Err(index) dizendo onde o valor ficaria.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("tem 31? {}", temps.contains(&31));
    println!("primeira acima de 20 em: {:?}", temps.iter().position(|&t| t > 20));
    println!("máx: {:?}, mín: {:?}", 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!("melhor jogador: {}", 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); // mantém a lista ordenada
    }
    println!("{:?}", sorted);
}

Saída:

tem 31? true
primeira acima de 20 em: Some(1)
máx: Some(31), mín: Some(12)
melhor jogador: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Experimente você mesmo

binary_search (busca binária) olha o item do meio, descarta a metade que não pode conter o valor e repete. Em uma lista de um milhão de itens, isso dá umas 20 verificações em vez de até um milhão. A resposta Err(pos) também é útil: inserir em pos mantém a lista ordenada.

Cuidado

max() e min() precisam de Ord, então também não funcionam com floats. Use max_by(|a, b| a.total_cmp(b)) no lugar, a mesma solução usada para ordenar.

Erros comuns

Devolver um campo String emprestado no sort_by_key. Parece natural, mas não compila:

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

O compilador diz que não pode mover s.name para fora de uma referência compartilhada. A closure só pega emprestado cada aluno, então não pode entregar a String dele. Ou você clona (|s| s.name.clone()), ou evita a cópia de vez com sort_by(|a, b| a.name.cmp(&b.name)).

Usar binary_search em uma lista não ordenada. Não vai travar, mas a resposta não tem sentido: ele pode dizer que um valor não está lá quando está. Sempre ordene antes, ou use contains / position.

Prática

1. Ranking

Você tem jogadores como tuplas (name, score) (nome, pontuação): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Ordene pela pontuação, da maior para a menor, desempatando pelo nome de A a Z. Imprima só os três primeiros. Dica: use sort_by com .then_with(), e uma slice &players[..3] para os três primeiros.

Ver solução

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}");
    }
}

Saída:

95 ana
88 dev
70 ben

▶ Experimente você mesmo

Em uma tupla, .0 é o nome e .1 é a pontuação. ben e chen têm 70, então o nome desempata e ben fica entre os três primeiros.

2. O preço mediano

Encontre a mediana (o valor do meio) dos preços 3.5, 1.25, 9.0, 4.75, 2.0. Imprima a lista ordenada e a mediana. Dica: ordene com total_cmp; depois, o item do meio de uma lista de tamanho ímpar fica no índice len() / 2.

Ver solução

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!("ordenados: {:?}", prices);
    println!("mediana: {median}");
}

Saída:

ordenados: [1.25, 2.0, 3.5, 4.75, 9.0]
mediana: 3.5

▶ Experimente você mesmo

A anotação de tipo Vec<f64> faz diferença. Sem ela, o Rust ainda não sabe qual é o tipo de float dos números quando chega em total_cmp, e se recusa a compilar com “no method named total_cmp” (não existe método chamado total_cmp).

Resumo

• sort() e sort_unstable() ordenam no lugar, do menor para o maior. Use reverse(), y.cmp(x) ou Reverse para começar pelo maior.
• Floats não podem usar sort() por causa do NaN. Use sort_by(|a, b| a.total_cmp(b)).
• sort_by_key ordena por um campo escolhido; sort_by com .then_with() ordena por vários campos.
• dedup() só remove vizinhos iguais, então ordene antes.
• contains, position, max/min e max_by_key buscam em qualquer lista; binary_search é muito mais rápido, mas precisa de uma lista ordenada.

Teste o que aprendeu

Teste o que aprendeu

1. Por que vec![1.5, 0.5].sort() não compila?

Floats não podem ser guardados em um Vec sort só funciona com strings Floats não implementam Ord, porque NaN não pode ser comparado O vetor não é mut

2. O que sobra no vetor depois de vec![1, 1, 2, 1].dedup()?

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. O que vec![10, 20, 30].binary_search(&25) devolve?

Err(2) Ok(2) None -1

4. Em a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), quando o nome é comparado?

Sempre, antes da nota Nunca Só quando os nomes são diferentes Só quando as duas notas são iguais

Pontuação: 0 / 4

Para saber mais

• Métodos de slice: sort, sort_by, binary_search e outros — documentação da std (em inglês): todos os métodos de ordenação e busca, com observações sobre velocidade e estabilidade.
• std::cmp::Ordering — documentação da std (em inglês): Less, Equal, Greater, além de then, then_with e reverse.
• std::cmp::Reverse — documentação da std (em inglês): o wrapper para ordenar uma chave da maior para a menor.
• f64::total_cmp — documentação da std (em inglês): onde exatamente NaN, o zero negativo e o infinito vão parar quando você ordena floats.
• Sort a Vector — Rust Cookbook (em inglês): receitas curtas para ordenar inteiros, floats e structs.