Bubble sort
Bubble sort adalah algoritma pengurutan yang paling mudah dijelaskan: bandingkan dua nilai bertetangga, tukar jika urutannya salah, lalu ulangi. Algoritma ini lambat pada daftar panjang, tetapi setiap langkahnya mudah diikuti, sehingga menjadi algoritma klasik pertama untuk diamati.
Idenya
Susuri daftar dari kiri ke kanan dan lihat setiap pasangan bertetangga. Jika nilai kiri lebih besar dari nilai kanan, tukar keduanya. Saat sampai di akhir, nilai terbesar sudah terbawa sampai ke tempat terakhir, seperti gelembung yang naik ke permukaan. Satu kali penyusuran itu disebut putaran. Ulangi putaran sampai daftar terurut.
Contoh
Ambil 5, 1, 4, 2, 8. Putaran pertama membandingkan 5 dan 1 lalu menukarnya, kemudian 5 dan 4 (tukar), 5 dan 2 (tukar), dan 5 dan 8 (tidak ditukar): 1, 4, 2, 5, 8. Angka 8 kini di tempat akhirnya. Putaran kedua membandingkan 1 dan 4 (tidak ditukar), 4 dan 2 (tukar), dan 4 dan 5 (tidak ditukar): 1, 2, 4, 5, 8. Putaran ketiga tidak melakukan penukaran sama sekali, jadi daftar sudah terurut: 9 perbandingan dan 4 penukaran.
Mengapa setiap putaran menempatkan satu nilai lagi
Selama satu putaran, nilai terbesar yang ditemui sejauh ini selalu ikut terbawa: begitu putaran mencapainya, setiap perbandingan memindahkannya satu tempat lagi ke kanan. Jadi putaran pertama menaruh nilai terbesar di akhir, putaran kedua menaruh nilai terbesar kedua tepat sebelumnya, dan seterusnya. Setelah putaran k, k tempat terakhir sudah final, dan putaran berikutnya bisa berhenti satu tempat lebih awal. Itulah mengapa putarannya makin pendek.
Penukaran sama dengan inversi
Inversi adalah pasangan nilai yang urutannya salah: nilai yang lebih besar berada di suatu tempat sebelum nilai yang lebih kecil. Menukar dua nilai bertetangga yang salah urutan menghapus tepat satu inversi dan tidak membuat inversi baru. Jadi bubble sort melakukan penukaran persis sebanyak inversi pada daftar awal, apa pun urutan perbandingannya. Daftar terurut tidak punya inversi; daftar terbalik berisi n nilai punya n(n − 1)/2, jumlah terbanyak yang mungkin.
Berhenti lebih awal dan biayanya
Jika satu putaran penuh tidak melakukan penukaran, setiap pasangan bertetangga sudah berurutan dan daftar sudah terurut. Dengan memeriksa hal itu, bubble sort bisa menyelesaikan daftar terurut dalam satu putaran berisi n − 1 perbandingan. Dalam kasus terburuk, algoritma ini tetap butuh n − 1 putaran dan n(n − 1)/2 perbandingan, dan rata-rata jumlah penukarannya n(n − 1)/4. Keduanya tumbuh sebanding dengan n², jadi menggandakan panjang daftar membuat pengurutan sekitar empat kali lebih lama.
Bubble sort bersifat stabil: nilai yang sama tidak pernah ditukar, jadi urutannya tetap. Algoritma ini mengurutkan di tempat tanpa memori tambahan. Insertion sort punya sifat yang sama dan biasanya butuh langkah lebih sedikit, sedangkan merge sort dan quicksort butuh waktu sebanding dengan n log n, yang jauh lebih sedikit pada daftar panjang.
Jelajahi
Buka aplikasinya dan tekan Putar, atau tekan Langkah untuk maju satu perbandingan setiap kali. Dua nilai yang sedang dibandingkan disorot, penukaran ditampilkan dengan warnanya sendiri, dan nilai yang sudah di tempatnya berubah hijau. Coba daftar terbalik untuk melihat kasus terburuk, daftar yang hampir terurut untuk melihat berhenti lebih awal mengakhiri pengurutan setelah beberapa putaran, atau ketik angka dari contoh di atas.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu bubble sort?
O(n²) pada kasus terburuk dan rata-rata: hingga n(n − 1)/2 perbandingan untuk n nilai. Dengan berhenti lebih awal, daftar yang sudah terurut butuh O(n), yaitu satu putaran. Memori tambahannya hanya O(1).
Apakah bubble sort stabil?
Ya. Algoritma ini menukar dua nilai bertetangga hanya jika yang kiri benar-benar lebih besar, jadi nilai yang sama tidak pernah saling melewati dan tetap dalam urutan aslinya.
Apa perbedaan bubble sort dan insertion sort?
Keduanya menukar nilai bertetangga dan keduanya melakukan penukaran sebanyak jumlah inversi. Bubble sort melakukan putaran penuh pada bagian yang belum terurut; insertion sort menggeser setiap nilai baru ke belakang hanya sejauh yang diperlukan, sehingga biasanya melakukan lebih sedikit perbandingan, terutama pada daftar yang hampir terurut.
Kapan bubble sort menjadi pilihan yang baik?
Terutama untuk pengajaran, dan untuk daftar yang sangat pendek ketika kesederhanaan lebih penting daripada kecepatan. Untuk yang lebih besar, fungsi pengurutan bawaan bahasa pemrograman Anda jauh lebih cepat.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba bubble sort