Sortieren und Suchen in Rust

Sortieren und Suchen brauchst du in fast jedem Programm: Spieler nach Punktzahl ordnen, Dateien nach Namen auflisten, das günstigste Produkt finden. Rust gibt Vektoren und Slices dafür eine ganze Reihe eingebauter Methoden mit. Einen eigenen Algorithmus musst du also nur selten schreiben.

Die meisten dieser Methoden nehmen ein Closure entgegen, das festlegt, wie zwei Elemente verglichen werden. Sobald du mit dieser einen Idee vertraut bist, ist der Rest der Seite nur noch eine Variation davon.

sort und sort_unstable

.sort() bringt die Elemente in aufsteigende Reihenfolge (das kleinste zuerst). Der Vektor wird dabei direkt verändert (in place), deshalb muss er mut sein. Zahlen werden nach ihrem Wert sortiert, Zeichenketten alphabetisch.

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

Ausgabe:

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

▶ Selbst ausprobieren

Zwei Dinge fallen auf:

• "adam" landet ganz hinten. Zeichenketten werden nach ihrem Zeichencode verglichen, und alle Großbuchstaben kommen vor allen Kleinbuchstaben. Willst du eine Reihenfolge wie im Wörterbuch, sortiere nach name.to_lowercase() (siehe weiter unten). Aus demselben Grund landen übrigens Umlaute wie „Ä“ oder „ü“ hinter „z“.
• sort_unstable ist meist etwas schneller und braucht keinen zusätzlichen Speicher. „Unstable“ (instabil) heißt nicht fehlerhaft. Es bedeutet nur, dass Elemente, die als gleich gelten, ihre Plätze tauschen können. Bei einfachen Zahlen oder Zeichenketten merkst du davon nichts – es ist also eine gute Standardwahl.

Umgekehrte Reihenfolge

Es gibt drei übliche Wege, vom größten zum kleinsten Wert zu sortieren. Hier liefern alle drei dasselbe Ergebnis.

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

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

Ausgabe:

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

▶ Selbst ausprobieren

x.cmp(y) gibt ein Ordering zurück: Less (kleiner), Equal (gleich) oder Greater (größer). Damit entscheidet sort_by, welches Element zuerst kommt. Schreibst du y.cmp(x), kehrst du jede einzelne Entscheidung um – und damit die ganze Reihenfolge. Reverse ist ein kleiner Wrapper aus std::cmp, der dasselbe für einen Schlüssel erledigt.

Floats sortieren

Rufst du .sort() auf einem Vektor aus f64 auf, weigert sich 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}`

Der Compiler sagt dir (auf Englisch), dass Fließkommazahlen den Trait Ord nicht implementieren. Warum? .sort() braucht eine totale Ordnung (den Trait Ord): Von zwei beliebigen Werten muss einer kleiner, gleich oder größer sein. Floats haben aber einen besonderen Wert, NaN („not a number“, keine Zahl), der weder kleiner noch gleich noch größer als irgendetwas ist – nicht einmal als er selbst. Floats haben deshalb nur PartialOrd, und .partial_cmp() gibt ein Option<Ordering> zurück, das bei NaN None ist.

Du hast zwei gute Lösungen:

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

    // Wenn du sicher bist, dass kein NaN vorkommt:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Funktioniert sogar mit NaN (NaN landet am Ende):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Ausgabe:

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

▶ Selbst ausprobieren

partial_cmp(...).unwrap() löst eine Panic aus, sobald es auf ein NaN trifft. total_cmp löst nie eine Panic aus, weil es jedem Float einen festen Platz zuweist, auch NaN. Nimm lieber total_cmp, außer du hast einen guten Grund dagegen.

sort_by_key und Structs sortieren

sort_by_key nimmt ein Closure, das auswählt, wonach sortiert wird. Das passt perfekt zu Structs, bei denen du dir ein Feld aussuchst.

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

Ausgabe:

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

▶ Selbst ausprobieren

Die Produktnamen bleiben auf Englisch, weil es hier genau auf die alphabetische Reihenfolge und die Groß- und Kleinschreibung ankommt.

Das Schlüssel-Closure muss einen Wert zurückgeben, der ihm selbst gehört (einen „owned“ Wert). p.price_cents ist ein u32 und wird kopiert – das passt. Für ein String-Feld brauchst du einen neuen String. Deshalb verwendet die zweite Sortierung to_lowercase(), das einen neuen erzeugt. (Mehr dazu unten bei den häufigen Fehlern.)

Nach mehreren Feldern sortieren

Eine klassische Aufgabe: Schüler nach Note sortieren, die höchste zuerst. Haben zwei Schüler dieselbe Note, sollen sie nach Namen sortiert werden, von A bis Z. Dafür nimmst du sort_by mit .then_with(). Der zweite Vergleich wird nur angeschaut, wenn der erste unentschieden ausgeht.

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)               // Note: von hoch nach niedrig
            .then_with(|| a.name.cmp(&b.name)) // dann Name: von A bis Z
    });

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

Ausgabe:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Selbst ausprobieren

Kürzer geht es, wenn du ein Tupel als Schlüssel zurückgibst. Tupel vergleichen zuerst das erste Element, dann das zweite und so weiter:

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

Das ergibt genau dieselbe Reihenfolge. Es ist schön kompakt, klont aber jeden Namen. Bei großen Listen ist sort_by mit then_with deshalb die bessere Gewohnheit.

Duplikate entfernen mit dedup

.dedup() entfernt Elemente, die gleich dem Element direkt davor sind. Alle Duplikate verschwinden also nur, wenn die Liste vorher sortiert ist.

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

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

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

Ausgabe:

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

▶ Selbst ausprobieren

Beim ersten Versuch wurden nur die beiden "web" zusammengefasst, die direkt nebeneinanderstanden. Also: erst sortieren, dann dedup. Musst du die ursprüngliche Reihenfolge behalten, nimm den HashSet-Trick von der Seite HashSet.

Suchen: contains, position, max, min, binary_search

Das sind die Suchwerkzeuge, die du am häufigsten brauchst:

• contains(&x) – ist es drin? Gibt einen bool zurück.
• iter().position(...) – wo ist der erste Treffer? Gibt Option<usize> zurück.
• iter().max() / iter().min() – größter und kleinster Wert, als Option (bei einer leeren Liste None).
• iter().max_by_key(...) / min_by_key(...) – größter oder kleinster Wert nach einem bestimmten Feld.
• binary_search(&x) – sehr schnelle Suche, aber nur auf einer sortierten Liste. Gibt Ok(index) zurück, wenn der Wert gefunden wurde, sonst Err(index) mit der Stelle, an die er gehören würde.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("enthält 31? {}", temps.contains(&31));
    println!("erster Wert über 20 an Index: {:?}", temps.iter().position(|&t| t > 20));
    println!("Maximum: {:?}, Minimum: {:?}", 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!("bester Spieler: {}", 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); // die Liste bleibt sortiert
    }
    println!("{:?}", sorted);
}

Ausgabe:

enthält 31? true
erster Wert über 20 an Index: Some(1)
Maximum: Some(31), Minimum: Some(12)
bester Spieler: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Selbst ausprobieren

binary_search (binäre Suche) prüft das mittlere Element, verwirft die Hälfte, in der der Wert nicht sein kann, und wiederholt das. Bei einer Liste mit einer Million Elementen sind das etwa 20 Prüfungen statt bis zu einer Million. Auch die Antwort Err(pos) ist praktisch: Fügst du an Position pos ein, bleibt die Liste sortiert.

Achtung

Auch max() und min() brauchen Ord und funktionieren deshalb nicht mit Floats. Nimm stattdessen max_by(|a, b| a.total_cmp(b)) – dieselbe Lösung wie beim Sortieren.

Häufige Fehler

Ein ausgeliehenes String-Feld aus sort_by_key zurückgeben. Das sieht naheliegend aus, kompiliert aber nicht:

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

Die Meldung (auf Englisch) heißt: Du kannst s.name nicht hinter einer geteilten Referenz herausbewegen. Das Closure leiht sich jeden Schüler nur aus und kann den String deshalb nicht weggeben. Entweder du klonst ihn (|s| s.name.clone()), oder du vermeidest die Kopie ganz mit sort_by(|a, b| a.name.cmp(&b.name)).

binary_search auf einer unsortierten Liste benutzen. Das stürzt nicht ab, aber die Antwort ist wertlos: Vielleicht heißt es, ein Wert fehle, obwohl er direkt vor dir liegt. Sortiere immer zuerst – oder nimm stattdessen contains / position.

Übungen

1. Bestenliste

Du hast Spieler als Tupel (name, score): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Sortiere sie nach Punktzahl, die höchste zuerst. Bei Gleichstand entscheidet der Name von A bis Z. Gib nur die ersten drei aus. Tipp: Nimm sort_by mit .then_with() und für die ersten drei den Slice &players[..3].

Lösung anzeigen

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

Ausgabe:

95 ana
88 dev
70 ben

▶ Selbst ausprobieren

Bei einem Tupel ist .0 der Name und .1 die Punktzahl. ben und chen haben beide 70. Also entscheidet der Name, und ben schafft es unter die ersten drei.

2. Der Medianpreis

Finde den Median (den mittleren Wert) der Preise 3.5, 1.25, 9.0, 4.75, 2.0. Gib die sortierte Liste und den Median aus. Tipp: Sortiere mit total_cmp. Bei einer Liste mit ungerader Länge liegt das mittlere Element dann bei Index len() / 2.

Lösung anzeigen

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

Ausgabe:

sortiert: [1.25, 2.0, 3.5, 4.75, 9.0]
Median: 3.5

▶ Selbst ausprobieren

Die Typangabe Vec<f64> ist wichtig. Ohne sie weiß Rust bei total_cmp noch nicht, welcher Float-Typ gemeint ist, und bricht mit „no method named total_cmp“ ab (es gibt keine Methode mit diesem Namen).

Zusammenfassung

• sort() und sort_unstable() sortieren direkt im Vektor, das kleinste Element zuerst. Für das größte zuerst nimmst du reverse(), y.cmp(x) oder Reverse.
• Floats können wegen NaN nicht sort() benutzen. Nimm sort_by(|a, b| a.total_cmp(b)).
• sort_by_key sortiert nach einem ausgewählten Feld, sort_by mit .then_with() nach mehreren Feldern.
• dedup() entfernt nur gleiche Nachbarn – also vorher sortieren.
• contains, position, max/min und max_by_key durchsuchen jede Liste. binary_search ist viel schneller, braucht aber eine sortierte Liste.

Kurzer Check

Kurzer Check

1. Warum kompiliert vec![1.5, 0.5].sort() nicht?

Floats kann man nicht in einem Vec speichern sort funktioniert nur mit Zeichenketten Floats implementieren Ord nicht, weil sich NaN nicht vergleichen lässt Der Vektor ist nicht mut

2. Was bleibt nach vec![1, 1, 2, 1].dedup() im Vektor übrig?

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

3. Was gibt vec![10, 20, 30].binary_search(&25) zurück?

Err(2) Ok(2) None -1

4. Wann wird in a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)) der Name verglichen?

Immer, noch vor der Note Nie Nur wenn die Namen verschieden sind Nur wenn die beiden Noten gleich sind

Punkte: 0 / 4

Weiterlesen

• Slice-Methoden: sort, sort_by, binary_search und mehr – Standardbibliothek (auf Englisch): alle Methoden zum Sortieren und Suchen, mit Hinweisen zu Geschwindigkeit und Stabilität.
• std::cmp::Ordering – Standardbibliothek (auf Englisch): Less, Equal, Greater sowie then, then_with und reverse.
• std::cmp::Reverse – Standardbibliothek (auf Englisch): der Wrapper, mit dem du einen Schlüssel vom größten zum kleinsten Wert sortierst.
• f64::total_cmp – Standardbibliothek (auf Englisch): wo genau NaN, negative Null und Unendlich landen, wenn du Floats sortierst.
• Sort a Vector – Rust Cookbook (auf Englisch): kurze Rezepte zum Sortieren von Ganzzahlen, Floats und Structs.