Gambaran Besar Dulu
Bayangkan kamu punya 8 teman berdiri berjajar, masing-masing pegang nomor. Tugasmu: urutkan mereka dari terkecil ke terbesar. Tapi kamu hanya boleh melihat dua orang berdampingan sekaligus, lalu tukar posisi kalau urutannya salah.
Itu persis cara kerja Bubble Sort.
Kenapa namanya “bubble” (gelembung)? Karena setiap putaran, angka terbesar akan terus berpindah ke kanan, satu langkah demi satu langkah, seperti gelembung udara yang naik ke permukaan air. Tidak langsung, tapi pasti sampai.
Konsep Inti: Dua Kata Kunci
Sebelum simulasi, kuasai dua kata ini dulu:
- Pass = satu putaran penuh memeriksa seluruh daftar dari kiri ke kanan
- Swap = menukar posisi dua elemen yang urutannya salah
Setiap kali satu pass selesai, satu angka terbesar sudah pasti ada di posisi yang benar (paling kanan dari area yang belum terurut). Jadi setiap pass berikutnya, area yang perlu diperiksa berkurang satu.
Simulasi Pass Demi Pass
Daftar awal: [5, 2, 8, 1, 9, 3, 7, 4]
Ada 8 elemen, artinya maksimal kita butuh 7 pass (n-1 = 8-1 = 7).
Pass 1 (periksa posisi 0 sampai 6, total 7 perbandingan)
| Langkah | Bandingkan | Aksi | Hasil Sementara |
|---|---|---|---|
| 1 | 5 vs 2 | 5 > 2, tukar | [2, 5, 8, 1, 9, 3, 7, 4] |
| 2 | 5 vs 8 | 5 < 8, biarkan | [2, 5, 8, 1, 9, 3, 7, 4] |
| 3 | 8 vs 1 | 8 > 1, tukar | [2, 5, 1, 8, 9, 3, 7, 4] |
| 4 | 8 vs 9 | 8 < 9, biarkan | [2, 5, 1, 8, 9, 3, 7, 4] |
| 5 | 9 vs 3 | 9 > 3, tukar | [2, 5, 1, 8, 3, 9, 7, 4] |
| 6 | 9 vs 7 | 9 > 7, tukar | [2, 5, 1, 8, 3, 7, 9, 4] |
| 7 | 9 vs 4 | 9 > 4, tukar | [2, 5, 1, 8, 3, 7, 4, 9] |
Hasil Pass 1: [2, 5, 1, 8, 3, 7, 4, 9]
Perhatikan: angka 9 sudah “menggelembung” sampai ke posisi paling kanan. Selesai. Tidak perlu diperiksa lagi.
Pass 2 (periksa posisi 0 sampai 5, karena posisi 6 sudah aman)
Daftar: [2, 5, 1, 8, 3, 7, 4, | 9]
| Langkah | Bandingkan | Aksi |
|---|---|---|
| 1 | 2 vs 5 | biarkan |
| 2 | 5 vs 1 | tukar → [2, 1, 5, …] |
| 3 | 5 vs 8 | biarkan |
| 4 | 8 vs 3 | tukar |
| 5 | 8 vs 7 | tukar |
| 6 | 8 vs 4 | tukar |
Hasil Pass 2: [2, 1, 5, 3, 7, 4, 8, 9]
Sekarang 8 dan 9 sudah di posisi benar. Pass 3 hanya perlu periksa 5 elemen pertama.
Melanjutkan Pass 3 sampai selesai
Pass 3: [1, 2, 3, 5, 4, 7, 8, 9]
Pass 4: [1, 2, 3, 4, 5, 7, 8, 9]
Pass 4 selesai, dan dalam Pass 5 tidak ada satu pun pertukaran. Ini sinyal bahwa daftar sudah terurut sempurna. Kita berhenti di sini, tidak perlu lanjut ke Pass 6 dan 7.
Optimasi: Berhenti Lebih Awal
Ini bagian pintarnya. Tambahkan satu “penanda” (misalnya variabel ada_swap):
- Tiap awal pass, set
ada_swap = False - Kalau ada pertukaran, set
ada_swap = True - Kalau pass selesai dan
ada_swapmasihFalse, artinya tidak ada yang perlu ditukar lagi. Daftar sudah terurut. Hentikan.
Ini yang membuat Bubble Sort bisa lebih efisien di kondisi data yang hampir terurut.
Hitung Perbandingan: Best Case vs Worst Case
| Kondisi | Jumlah Pass | Total Perbandingan | Keterangan |
|---|---|---|---|
| Best case | 1 pass | n-1 = 7 | Data sudah terurut sejak awal |
| Worst case | n-1 pass | n(n-1)/2 = 28 | Data terbalik (8,7,6,5,4,3,2,1) |
Untuk 8 elemen: worst case = 8 × 7 / 2 = 28 perbandingan.
Perbandingan dengan Tiga Algoritma Sorting
| Algoritma | Cara Kerja | Analogi |
|---|---|---|
| Bubble Sort | Bandingkan dua elemen berdampingan, tukar jika salah | Gelembung naik ke permukaan air |
| Insertion Sort | Ambil satu elemen, sisipkan ke posisi yang tepat di bagian yang sudah terurut | Menyusun kartu remi satu per satu di tangan |
| Selection Sort | Cari elemen terkecil dari seluruh sisa daftar, taruh di posisi paling kiri | Pilih nilai ujian terkecil satu per satu, tempel di papan |
Dari ketiga ini, Bubble Sort paling mudah dipahami secara visual. Selection Sort lebih sedikit melakukan swap dibanding Bubble Sort. Insertion Sort paling efisien kalau datanya hampir terurut.
Aktivitas Fisik di Kelas
8 siswa berdiri berjajar, masing-masing pegang kertas bertuliskan angka dari daftar [5, 2, 8, 1, 9, 3, 7, 4].
Cara bermain:
- Mulai dari kiri, guru sebut “bandingkan posisi 1 dan 2.”
- Dua siswa itu tunjukkan angka mereka. Kalau yang kiri lebih besar, mereka tukar tempat.
- Geser ke kanan: “bandingkan posisi 2 dan 3.” Dan seterusnya sampai ujung kanan.
- Itu satu pass. Siswa paling kanan yang sudah di posisi benar boleh duduk.
- Ulangi dari awal untuk siswa yang masih berdiri.
Perhatikan bagaimana siswa dengan angka terbesar “berjalan” ke kanan setiap pass.
Jebakan Umum yang Sering Terjadi
-
Lupa mengurangi area pemeriksaan. Setelah pass 1, angka terakhir sudah aman, tidak perlu ikut diperiksa lagi. Kalau tetap diperiksa sampai akhir, program tetap benar tapi lebih lambat dari seharusnya.
-
Tidak pakai penanda swap. Tanpa penanda, program akan terus jalan sampai pass ke n-1 meski data sudah terurut dari pass ke-3. Buang-buang waktu.
-
Bingung arah perbandingan. Untuk urutan naik (ascending), kita tukar kalau elemen kiri lebih BESAR dari kanan. Kalau terbalik, hasilnya urutan menurun (descending), bukan yang diminta.
-
Salah menghitung jumlah pass. Untuk n elemen, maksimal butuh n-1 pass, bukan n pass.
Kuis Pemahaman
-
Daftar
[3, 1, 4, 1, 5, 9]diproses dengan Bubble Sort. Setelah Pass 1 selesai, angka berapa yang sudah pasti berada di posisi terakhir dan kenapa? -
Kalau data awal sudah terurut sempurna seperti
[1, 2, 3, 4, 5], berapa minimum pass yang dibutuhkan Bubble Sort (dengan optimasi penanda swap)? Dan berapa total perbandingan yang terjadi? -
Apa perbedaan mendasar cara kerja Bubble Sort dengan Selection Sort? Beri satu contoh konkret yang menjelaskan perbedaan itu.