Ir al contenido
Ferris the Rust crabTutorial de Rust

Ordenar y buscar en Rust

Ordenar y buscar son dos tareas que harás en casi cualquier programa: clasificar jugadores por puntuación, listar archivos por nombre, encontrar el producto más barato. Rust les da a los vectores y a los slices un conjunto de métodos integrados para ambas cosas, así que casi nunca tendrás que escribir tu propio algoritmo.

La mayoría de estos métodos reciben una closure que dice cómo comparar dos elementos. En cuanto te sientas cómodo con esa idea, el resto de la página son solo variaciones sobre ella.

sort y sort_unstable

Sección titulada «sort y sort_unstable»

.sort() pone los elementos en orden ascendente (el más pequeño primero). Modifica el vector en el sitio (in place), así que el vector tiene que ser mut. Los números se ordenan por su valor; las cadenas de texto, alfabéticamente.

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

Salida:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]
▶ Pruébalo tú mismo

Fíjate en dos cosas:

  • "adam" sale al final. Las cadenas se comparan por el código de cada carácter, y todas las mayúsculas van antes que todas las minúsculas. Por la misma razón, las letras con tilde o la “ñ” quedan detrás de la “z”. Ordena por name.to_lowercase() (lo verás más abajo) si quieres un orden “de diccionario”.
  • sort_unstable suele ser un poco más rápido y no usa memoria extra. “Unstable” (inestable) no significa que tenga fallos. Significa que los elementos que se consideran iguales pueden intercambiar su posición. Con números o cadenas simples no notarás la diferencia, así que es una buena opción por defecto.

Orden inverso

Sección titulada «Orden inverso»

Hay tres formas habituales de ordenar de mayor a menor. Aquí las tres dan el mismo 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 que x = descendente
    println!("{:?}", b);


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

Salida:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]
▶ Pruébalo tú mismo

x.cmp(y) devuelve un Ordering: Less (menor), Equal (igual) o Greater (mayor). sort_by lo usa para decidir qué elemento va primero. Escribir y.cmp(x) invierte cada decisión, y con eso se invierte el orden completo. Reverse es un pequeño envoltorio de std::cmp que hace la misma inversión para una clave.

Ordenar números decimales (floats)

Sección titulada «Ordenar números decimales (floats)»

Prueba .sort() con un vector de f64 y Rust se niega:

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

El compilador te dice que los floats no implementan el trait Ord. ¿Por qué? .sort() necesita un orden total (el trait Ord): para dos valores cualesquiera, uno tiene que ser menor, igual o mayor que el otro. Los floats tienen un valor especial, NaN (“not a number”, no es un número), que no es menor, ni igual, ni mayor que nada, ni siquiera que sí mismo. Por eso los floats solo tienen PartialOrd, y .partial_cmp() devuelve un Option<Ordering> que vale None cuando aparece un NaN.

Tienes dos buenas soluciones:

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


    // Si estás seguro de que no hay ningún NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);


    // Funciona incluso con NaN (el NaN va al final):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Salida:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]
▶ Pruébalo tú mismo

partial_cmp(...).unwrap() hará panic si se encuentra un NaN. total_cmp nunca hace panic, porque define un lugar fijo para cada float, incluido NaN. Usa total_cmp a menos que tengas un motivo para no hacerlo.

sort_by_key y ordenar structs

Sección titulada «sort_by_key y ordenar structs»

sort_by_key recibe una closure que elige por qué ordenar. Es perfecto para los structs, donde eliges un campo.

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


fn main() {
    let mut items = vec![
        Product { name: String::from("pluma"), price_cents: 150 },
        Product { name: String::from("Libreta"), price_cents: 499 },
        Product { name: String::from("goma"), 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);
}

Salida:

75 - goma
150 - pluma
499 - Libreta
["goma", "Libreta", "pluma"]
▶ Pruébalo tú mismo

La closure de la clave tiene que devolver un valor con dueño (owned). p.price_cents es un u32, que se copia, así que no hay problema. Para un campo String necesitas un String nuevo, y por eso el segundo ordenamiento usa to_lowercase(), que crea uno. (Mira la sección de errores comunes más abajo).

Ordenar por varios campos

Sección titulada «Ordenar por varios campos»

Una tarea clásica: ordenar a los estudiantes por nota, de mayor a menor, y cuando dos tienen la misma nota, ordenarlos por nombre de la A a la Z. Usa sort_by con .then_with(). Solo mira la segunda comparación cuando la primera queda empatada.

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: de mayor a menor
            .then_with(|| a.name.cmp(&b.name)) // luego nombre: de la A a la Z
    });


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

Salida:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia
▶ Pruébalo tú mismo

Una alternativa más corta es devolver una tupla como clave. Las tuplas comparan el primer elemento, luego el segundo, y así sucesivamente:

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

Esto da exactamente el mismo orden. Queda limpio, pero clona cada nombre, así que sort_by con then_with es mejor costumbre para listas grandes.

Quitar duplicados con dedup

Sección titulada «Quitar duplicados con dedup»

.dedup() quita los elementos que son iguales al que tienen justo antes. Por eso solo elimina todos los duplicados si la lista está ordenada primero.

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


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


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

Salida:

solo dedup:   ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]
▶ Pruébalo tú mismo

En el primer intento solo se juntaron los dos "web" que estaban uno al lado del otro. Primero ordena y luego aplica dedup. Si necesitas conservar el orden original, usa el truco del HashSet de la página de HashSet.

Sección titulada «Buscar: contains, position, max, min, binary_search»

Estas son las herramientas de búsqueda que más vas a usar:

  • contains(&x): ¿está ahí? Devuelve un bool.
  • iter().position(...): ¿dónde está la primera coincidencia? Devuelve un Option<usize>.
  • iter().max() / iter().min(): el mayor y el menor, como un Option (es None si la lista está vacía).
  • iter().max_by_key(...) / min_by_key(...): el mayor o el menor según algún campo.
  • binary_search(&x): búsqueda muy rápida, pero solo en una lista ordenada. Devuelve Ok(índice) si lo encuentra, o Err(índice) indicando dónde iría.
fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("¿hay un 31? {}", temps.contains(&31));
    println!("primero mayor que 20 en: {:?}", 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!("mejor jugador: {}", 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); // mantiene la lista ordenada
    }
    println!("{:?}", sorted);
}

Salida:

¿hay un 31? true
primero mayor que 20 en: Some(1)
máx: Some(31), mín: Some(12)
mejor jugador: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]
▶ Pruébalo tú mismo

binary_search (búsqueda binaria) mira el elemento del medio, descarta la mitad donde el valor no puede estar, y repite. En una lista de un millón de elementos son unas 20 comprobaciones, en lugar de hasta un millón. La respuesta Err(pos) también es muy práctica: si insertas en pos, la lista sigue ordenada.

Errores comunes

Sección titulada «Errores comunes»

Devolver un campo String prestado desde sort_by_key. Parece lo natural, pero no 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

El compilador te dice que no puede mover s.name fuera de una referencia compartida. La closure solo toma prestado cada estudiante, así que no puede regalar su String. O lo clonas (|s| s.name.clone()), o evitas la copia por completo con sort_by(|a, b| a.name.cmp(&b.name)).

Usar binary_search en una lista sin ordenar. No va a fallar, pero la respuesta no tiene sentido: puede decirte que un valor no está cuando está justo ahí. Ordena siempre primero, o usa contains / position en su lugar.

Práctica

Sección titulada «Práctica»

1. Tabla de clasificación

Sección titulada «1. Tabla de clasificación»

Tienes jugadores como tuplas (nombre, puntuación): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Ordénalos por puntuación, de mayor a menor, y en caso de empate por nombre de la A a la Z. Imprime solo los tres primeros. Pista: usa sort_by con .then_with(), y un slice &players[..3] para los tres primeros.

Ver solución
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}");
    }
}

Salida:

95 ana
88 dev
70 ben
▶ Pruébalo tú mismo

En una tupla, .0 es el nombre y .1 es la puntuación. ben y chen tienen 70 los dos, así que el nombre desempata y ben entra entre los tres primeros.

2. El precio mediano

Sección titulada «2. El precio mediano»

Encuentra la mediana (el valor del medio) de los precios 3.5, 1.25, 9.0, 4.75, 2.0. Imprime la lista ordenada y la mediana. Pista: ordena con total_cmp; en una lista de longitud impar, el elemento del medio está en el índice len() / 2.

Ver solución
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}");
}

Salida:

ordenados: [1.25, 2.0, 3.5, 4.75, 9.0]
mediana: 3.5
▶ Pruébalo tú mismo

La anotación de tipo Vec<f64> importa. Sin ella, Rust todavía no sabe de qué tipo de float son los números cuando llega a total_cmp, y se niega a compilar con “no method named total_cmp” (no existe un método llamado total_cmp).

Resumen

Sección titulada «Resumen»
  • sort() y sort_unstable() ordenan en el sitio, de menor a mayor. Usa reverse(), y.cmp(x) o Reverse para ordenar de mayor a menor.
  • Los floats no pueden usar sort() por culpa de NaN. Usa sort_by(|a, b| a.total_cmp(b)).
  • sort_by_key ordena por el campo que elijas; sort_by con .then_with() ordena por varios campos.
  • dedup() solo quita los vecinos que son iguales, así que ordena primero.
  • contains, position, max/min y max_by_key buscan en cualquier lista; binary_search es mucho más rápido, pero necesita una lista ordenada.

Comprueba lo que aprendiste

Sección titulada «Comprueba lo que aprendiste»

Comprueba lo aprendido

1. ¿Por qué vec![1.5, 0.5].sort() no compila?

2. ¿Qué queda en el vector después de vec![1, 1, 2, 1].dedup()?

3. ¿Qué devuelve vec![10, 20, 30].binary_search(&25)?

4. En a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), ¿cuándo se compara el nombre?

Puntuación: 0 / 4

Para leer más

Sección titulada «Para leer más»