Bead Sort (Sortir Gravitasi)
Bead Sort (sortir manik / gravitasi) adalah algoritma pengurutan bilangan bulat non-negatif. Tiap angka digambarkan sebagai deretan manik pada satu baris (rata kiri). Saat "gravitasi" diterapkan, manik pada tiap kolom jatuh ke dasar. Setelah semua manik jatuh, tinggi (jumlah manik) tiap baris dari atas ke bawah menjadi terurut menaik. Kompleksitas O(n * maks).
Ilustrasi "sorting network" / analog abacus: tiap kolom bekerja mandiri sehingga dapat diparalelkan atau diimplementasi di perangkat keras. Contoh: [4,2,5,1,3] -> gravitasi -> [1,2,3,4,5]. Terbatas untuk bilangan bulat non-negatif yang kecil.
Menggambarkan tiap angka sebagai tumpukan manik lalu membiarkan gravitasi menjatuhkannya, sehingga baris otomatis terurut menaik.
- ·Memahami cara merepresentasikan bilangan sebagai deretan manik
- ·Menjelaskan bagaimana 'gravitasi' per kolom menghasilkan urutan
- ·Menerapkan idenya pada bilangan bulat non-negatif yang kecil
- ·Tiap angka jadi satu baris manik, rata kiri
- ·Bayangkan gravitasi menarik semua manik ke bawah
- ·Manik di tiap kolom jatuh mengisi baris paling bawah dulu
- ·Setelah semua jatuh, hitung manik tiap baris dari atas
- ·Tinggi baris kini terurut menaik: [4,2,5,1,3] jadi [1,2,3,4,5]
- ·Bilangan bulat non-negatif
- ·Analog sempoa (abacus) yang manik-maniknya turun sendiri
- ·Ilustrasi tiap kolom bekerja mandiri seperti mesin sederhana
Kompleksitas O(n * maks)