Bubble Sort di Rust

Salah satu implementasi algoritma yang biasa dilakukan oleh programmer pemula biasanya adalah mengimplementasikan sorting algorithm

Salah satunya yang paling mudah adalah bubble sort, yang dapat diimplementasikan biasanya kurang dari 50 baris kode walaupun performanya bisa dibilang paling jelek

Secara umum cara kerja dari bubble sort adalah “lakukan sorting terus menerus hingga tidak ada yang bisa di sorting lagi”, bisa dibilang sejenis metode brute force

Aku buatin ilustrasi cara kerja algoritma ini dalam bentuk animasi, atau bisa kalian download dibawah

Versi Sederhana

Versi sederhana diimplementasikan dengan mempergunakan fungsi seperti biasa, data disimpan dalam sebuah vektor dimana setiap item dalam vektor harus mengimplementasikan trait Ord

Tipe data yang mengimplementasikan trait Ord memiliki implementasikan terhadap operator perbandinga > dan < yang mana kita perlukan untuk mengurutkan item di dalam vektor tadi

fn bubble_sort(data: &mut Vec<impl Ord>) {
    let mut sorted = false;

    while !sorted {
        sorted = true;

        for i in 0..(data.len() - 1) {
            if data[i] > data[i + 1] {
                data.swap(i, i + 1);
                sorted = false;
            }
        }
    }
}

fn main() {
    let mut dataset = vec![3, 8, 10, 2, 3, 11, 38, -5];
    println!("Dataset: {:?}", dataset);

    bubble_sort(&mut dataset);
    println!("Bubble sorted: {:?}", dataset);

    let sorted = vec![-5, 2, 3, 3, 8, 10, 11, 38];
    assert_eq!(dataset, sorted);

    println!("Hello, world!");
}

Menjalankan kode diatas akan menghasilkan output sebagai berikut

Versi Fleksibel

Versi fleksibel diimplementasikan dengan membuat sebuah trait sendiri BubblyOrderable dan item yang diurutkan berada di dalam sebuah vektor dimana setiap item dalam vektor harus mengimplementasikan PartialOrd (Mengimplementasikan operator perbandingan)

Misal sebagian besar tipe data primitif di Rust sudah mengimplementasikan trait PartialOrd seperti int (Contoh diatas), apabila membuat sebuah tipe data baru seperti Kartu dalam contoh ini, maka operator perbandingan antara 2 kartu perlu diimplementasikan sendiri (Lihat bagian impl PartialOrd dan PartialEq for Kartu)

Kenapa BubblySorty ditaruh didalam sebuah trait? Tujuannya adalah biar bisa fleksibel dipake dimanapun, misalnya untuk mengatasi Orphan rule nya Rust.

Dan karena diimplementasikan sebagai trait dan bukan fungsi seperti biasa, kita bisa memanggil fungsi bubbly_sorty dari vektor yang memenuhi T tadi, misalkan di main kita membuat sebuah vektor, dan dalam vektor ini otomatis memiliki fungsi bubbly_sorty yang merupakan fungsi custom yang kita implementasikan.

Perhatikan jika kita sedang berada di crate eksternal, maka trait BubblyOrderable mungkin tak otomatis di-import dan karena itu fungsi bubbly_sorty tidak akan ada dalam vektor baru yang kita buat. Untuk mengatasinya dalam diimport trait ini (Sebelum itu ubah traitnya menjadi publik)

// #[derive(Debug)]
struct Kartu {
    is_merah: bool,
    number: u8,
}
impl std::fmt::Debug for Kartu {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let s = if self.is_merah { "Merah" } else { "Hitam" };
        f.write_str(s)?;
        f.write_str(" ")?;
        f.write_str(self.number.to_string().as_str())
    }
}

impl Kartu {
    fn new(is_merah: bool, number: u8) -> Kartu {
        Kartu { is_merah, number }
    }
}

impl PartialOrd for Kartu {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.number.partial_cmp(&other.number)
    }
}
impl PartialEq for Kartu {
    fn eq(&self, other: &Self) -> bool {
        self.is_merah == other.is_merah && self.number == other.number
    }
}

trait BubblyOrderable {
    fn bubbly_sorty(&mut self);
}

impl<T> BubblyOrderable for Vec<T>
where
    T: PartialOrd,
{
    fn bubbly_sorty(&mut self) {
        let mut sorted = false;
        while sorted == false {
            sorted = true;
            for i in 0..(self.len() - 1) {
                if self[i] > self[i + 1] {
                    self.swap(i, i + 1);
                    sorted = false;
                }
            }
        }
    }
}

fn main() {
    let a = Kartu::new(true, 1);
    let b = Kartu::new(false, 10);
    let c = Kartu::new(false, 4);
    let d = Kartu::new(true, 7);

    let mut arr = vec![a, b, c, d]; // len = 9

    println!("Sebelum {:?}", arr);

    // bubble_sort(&mut arr);
    arr.bubbly_sorty();

    let mut arr2 = vec![0, 4, 501, 3, -5];
    arr2.bubbly_sorty();

    println!("Sesudah {:?}", arr);
}

Hasil running kode diatas akan menghasilkan output seperti berikut

Leave a Comment