Mengurutkan dan Mencari di Rust

Mengurutkan (sorting) dan mencari (searching) adalah dua tugas yang akan kamu lakukan di hampir setiap program: memberi peringkat pemain berdasarkan skor, menampilkan file berdasarkan nama, mencari produk termurah. Rust membekali vektor dan slice dengan sekumpulan method bawaan untuk keduanya, jadi kamu jarang perlu menulis algoritma sendiri.

Kebanyakan method ini menerima sebuah closure (fungsi anonim) yang menjelaskan bagaimana cara membandingkan dua item. Begitu kamu terbiasa dengan satu ide itu, sisa halaman ini hanyalah variasinya.

sort dan sort_unstable

.sort() menyusun item secara menaik (yang terkecil lebih dulu). Method ini mengubah vektor di tempat (in place), jadi vektornya harus mut. Angka diurutkan berdasarkan nilainya; string diurutkan berdasarkan abjad.

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

Output:

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

▶ Coba sendiri

Ada dua hal yang perlu diperhatikan:

• "adam" muncul paling akhir. String dibandingkan berdasarkan kode karakternya, dan semua huruf kapital ada sebelum semua huruf kecil. Urutkan berdasarkan name.to_lowercase() (lihat di bawah) kalau kamu ingin urutan “seperti kamus”.
• sort_unstable biasanya sedikit lebih cepat dan tidak memakai memori tambahan. “Unstable” bukan berarti penuh bug. Artinya, item yang dianggap sama bisa saja bertukar posisi. Untuk angka atau string biasa, kamu tidak akan melihat bedanya, jadi ini pilihan default yang baik.

Urutan terbalik

Ada tiga cara umum untuk mengurutkan dari yang terbesar ke yang terkecil. Di sini ketiganya memberi hasil yang sama.

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

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

Output:

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

▶ Coba sendiri

x.cmp(y) mengembalikan sebuah Ordering: Less, Equal, atau Greater. sort_by memakainya untuk memutuskan item mana yang lebih dulu. Menulis y.cmp(x) membalik setiap keputusan, sehingga seluruh urutannya ikut terbalik. Reverse adalah pembungkus kecil dari std::cmp yang melakukan pembalikan yang sama untuk sebuah key.

Mengurutkan float

Coba panggil .sort() pada vektor berisi f64, dan Rust akan menolaknya:

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

Pesan error ini berarti tipe float tidak mengimplementasikan trait Ord. Kenapa? .sort() butuh urutan total (trait Ord): untuk dua nilai apa pun, salah satunya harus lebih kecil, sama, atau lebih besar. Float punya nilai khusus, NaN (“not a number”, bukan angka), yang tidak lebih kecil, tidak sama dengan, dan tidak lebih besar dari apa pun, bahkan dari dirinya sendiri. Karena itu float hanya punya PartialOrd, dan .partial_cmp() mengembalikan Option<Ordering> yang bernilai None untuk NaN.

Ada dua solusi yang bagus:

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

    // Kalau kamu yakin tidak ada NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Tetap jalan walaupun ada NaN (NaN ditaruh di akhir):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Output:

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

▶ Coba sendiri

partial_cmp(...).unwrap() akan panic kalau bertemu NaN. total_cmp tidak pernah panic karena ia menetapkan tempat yang pasti untuk setiap float, termasuk NaN. Utamakan total_cmp, kecuali kamu punya alasan untuk tidak memakainya.

sort_by_key dan mengurutkan struct

sort_by_key menerima closure yang memilih apa yang dijadikan dasar pengurutan. Ini sangat cocok untuk struct, karena kamu tinggal memilih salah satu field-nya.

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

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

Output:

75 - penghapus
150 - pulpen
499 - Spidol
["penghapus", "pulpen", "Spidol"]

▶ Coba sendiri

Dengan to_lowercase(), "Spidol" berada di urutan yang benar menurut abjad. Dengan sort() biasa, ia akan naik ke posisi pertama karena huruf kapitalnya.

Closure untuk key harus mengembalikan nilai yang dimiliki sendiri (owned). p.price_cents bertipe u32, yang disalin, jadi aman. Untuk field String, kamu butuh String baru. Itulah sebabnya pengurutan kedua memakai to_lowercase(), yang membuat String baru. (Lihat bagian kesalahan umum di bawah.)

Mengurutkan berdasarkan beberapa field

Tugas klasik: urutkan siswa berdasarkan nilai, tertinggi lebih dulu, dan kalau dua siswa punya nilai yang sama, urutkan berdasarkan nama dari A ke Z. Pakai sort_by dengan .then_with(). Method ini hanya melihat perbandingan kedua kalau perbandingan pertama hasilnya seri.

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

fn main() {
    let mut class = vec![
        Student { name: String::from("Budi"), grade: 88 },
        Student { name: String::from("Ayu"), grade: 95 },
        Student { name: String::from("Rudi"), grade: 88 },
        Student { name: String::from("Dewi"), grade: 88 },
        Student { name: String::from("Sinta"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // nilai: tinggi ke rendah
            .then_with(|| a.name.cmp(&b.name)) // lalu nama: A ke Z
    });

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

Output:

 95  Ayu
 88  Budi
 88  Dewi
 88  Rudi
 72  Sinta

▶ Coba sendiri

Alternatif yang lebih singkat adalah mengembalikan sebuah tuple sebagai key. Tuple membandingkan item pertama, lalu item kedua, dan seterusnya:

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

Hasil urutannya persis sama. Cara ini rapi, tetapi meng-clone setiap nama, jadi sort_by dengan then_with adalah kebiasaan yang lebih baik untuk daftar yang besar.

Menghapus duplikat dengan dedup

.dedup() menghapus item yang sama dengan item tepat sebelumnya. Jadi method ini hanya menghapus semua duplikat kalau daftarnya sudah diurutkan lebih dulu.

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

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

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

Output:

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

▶ Coba sendiri

Pada percobaan pertama, hanya dua item "web" yang bersebelahan yang digabung. Urutkan dulu, baru dedup. Kalau kamu perlu mempertahankan urutan aslinya, pakai trik HashSet dari halaman HashSet.

Mencari: contains, position, max, min, binary_search

Berikut alat pencarian yang paling sering kamu pakai:

• contains(&x): apakah nilainya ada? Mengembalikan bool.
• iter().position(...): di mana kecocokan pertamanya? Mengembalikan Option<usize>.
• iter().max() / iter().min(): nilai terbesar dan terkecil, dalam bentuk Option (bernilai None untuk daftar kosong).
• iter().max_by_key(...) / min_by_key(...): terbesar atau terkecil berdasarkan suatu field.
• binary_search(&x): pencarian yang sangat cepat, tetapi hanya untuk daftar yang sudah terurut. Mengembalikan Ok(index) kalau ketemu, atau Err(index) yang menunjukkan di mana nilai itu seharusnya berada.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("ada 31? {}", temps.contains(&31));
    println!("pertama di atas 20 di: {:?}", temps.iter().position(|&t| t > 20));
    println!("maks: {:?}, min: {:?}", 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!("pemain teratas: {}", 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); // daftarnya tetap terurut
    }
    println!("{:?}", sorted);
}

Output:

ada 31? true
pertama di atas 20 di: Some(1)
maks: Some(31), min: Some(12)
pemain teratas: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Coba sendiri

binary_search memeriksa item yang di tengah, membuang separuh daftar yang tidak mungkin berisi nilai itu, lalu mengulanginya. Pada daftar berisi sejuta item, itu hanya sekitar 20 kali pemeriksaan, bukan sampai sejuta kali. Jawaban Err(pos) juga berguna: memasukkan nilai di pos membuat daftarnya tetap terurut.

Perhatian

max() dan min() butuh Ord, jadi keduanya juga tidak bisa dipakai pada float. Pakai max_by(|a, b| a.total_cmp(b)) sebagai gantinya, solusi yang sama seperti saat mengurutkan.

Kesalahan umum

Mengembalikan field String yang sedang dipinjam dari sort_by_key. Kelihatannya wajar, tetapi tidak bisa di-compile:

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

Compiler bilang ia tidak bisa memindahkan s.name keluar dari referensi yang sedang dipinjam. Closure ini hanya meminjam setiap siswa, jadi ia tidak bisa menyerahkan String-nya begitu saja. Kamu bisa meng-clone-nya (|s| s.name.clone()) atau menghindari penyalinan sama sekali dengan sort_by(|a, b| a.name.cmp(&b.name)).

Memakai binary_search pada daftar yang belum terurut. Programnya tidak akan crash, tetapi jawabannya tidak ada artinya: bisa saja ia bilang sebuah nilai tidak ada padahal nilainya jelas ada di sana. Selalu urutkan dulu, atau pakai contains / position.

Latihan

1. Papan peringkat

Kamu punya data pemain dalam bentuk tuple (nama, skor): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Urutkan berdasarkan skor, tertinggi lebih dulu, dan kalau seri urutkan berdasarkan nama dari A ke Z. Cetak tiga teratas saja. Petunjuk: pakai sort_by dengan .then_with(), dan slice &players[..3] untuk tiga teratas.

Lihat solusi

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

Output:

95 ana
88 dev
70 ben

▶ Coba sendiri

Pada tuple, .0 adalah nama dan .1 adalah skor. ben dan chen sama-sama punya 70, jadi nama yang menentukan, dan ben masuk tiga besar.

2. Harga median

Cari median (nilai tengah) dari harga 3.5, 1.25, 9.0, 4.75, 2.0. Cetak daftar yang sudah terurut beserta median-nya. Petunjuk: urutkan dengan total_cmp; pada daftar dengan panjang ganjil, item tengahnya ada di indeks len() / 2.

Lihat solusi

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

Output:

terurut: [1.25, 2.0, 3.5, 4.75, 9.0]
median: 3.5

▶ Coba sendiri

Anotasi tipe Vec<f64> itu penting. Tanpanya, Rust belum tahu tipe float mana yang dipakai saat sampai di total_cmp, dan ia menolak meng-compile dengan pesan “no method named total_cmp” (tidak ada method bernama total_cmp).

Ringkasan

• sort() dan sort_unstable() mengurutkan di tempat, dari yang terkecil. Pakai reverse(), y.cmp(x), atau Reverse untuk mulai dari yang terbesar.
• Float tidak bisa memakai sort() karena adanya NaN. Pakai sort_by(|a, b| a.total_cmp(b)).
• sort_by_key mengurutkan berdasarkan field yang dipilih; sort_by dengan .then_with() mengurutkan berdasarkan beberapa field.
• dedup() hanya menghapus item bersebelahan yang sama, jadi urutkan dulu.
• contains, position, max/min, dan max_by_key bisa mencari di daftar apa pun; binary_search jauh lebih cepat tetapi butuh daftar yang sudah terurut.

Kuis singkat

Kuis singkat

1. Kenapa vec![1.5, 0.5].sort() gagal di-compile?

Float tidak bisa disimpan di Vec sort hanya bekerja untuk string Float tidak mengimplementasikan Ord, karena NaN tidak bisa dibandingkan Vektornya tidak mut

2. Apa yang tersisa di vektor setelah vec![1, 1, 2, 1].dedup()?

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

3. Apa yang dikembalikan vec![10, 20, 30].binary_search(&25)?

Err(2) Ok(2) None -1

4. Pada a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), kapan nama dibandingkan?

Selalu, sebelum nilai Tidak pernah Hanya kalau namanya berbeda Hanya kalau kedua nilainya sama

Skor: 0 / 4

Bacaan lebih lanjut

• Method slice: sort, sort_by, binary_search, dan lainnya — dokumentasi standard library (bahasa Inggris): semua method untuk mengurutkan dan mencari, dengan catatan soal kecepatan dan stabilitas.
• std::cmp::Ordering — dokumentasi standard library (bahasa Inggris): Less, Equal, Greater, plus then, then_with, dan reverse.
• std::cmp::Reverse — dokumentasi standard library (bahasa Inggris): pembungkus untuk mengurutkan key dari yang terbesar ke yang terkecil.
• f64::total_cmp — dokumentasi standard library (bahasa Inggris): posisi persis NaN, nol negatif, dan tak hingga saat kamu mengurutkan float.
• Sort a Vector — Rust Cookbook (bahasa Inggris): resep singkat untuk mengurutkan integer, float, dan struct.