Pengurutan gelembung
Menelusuri daftar berulang kali dan menukar dua nilai bersebelahan yang urutannya salah. Setelah tiap putaran, nilai terbesar yang tersisa ada di ujung.
- terbaik Ω(n)
- rata-rata Θ(n²)
- terburuk O(n²)
- memori O(1)
- stabil
- tanpa memori tambahan
Apa artinya?
- Kasus terbaik: bagaimana waktu tumbuh seiring ukuran daftar n saat input paling mudah bagi algoritma ini.
- Rata-rata: pertumbuhan waktu biasa terhadap n. Pada n², jumlah nilai 2 kali lipat butuh sekitar 4 kali waktu; n log n jauh lebih lambat.
- Kasus terburuk: pertumbuhan pada input tersulit. Berguna saat kecepatan tidak boleh turun.
- Memori: berapa memori tambahan yang dibutuhkan selain daftar. 1 berarti beberapa variabel, n berarti salinan daftar.
- Stabil: dua nilai yang sama tetap dalam urutan aslinya. Penting saat mengurutkan data menurut satu kolom.
- Tanpa memori tambahan: mengurutkan di dalam daftar itu sendiri, tanpa daftar kedua.
- dibandingkan
- dipindahkan
- di posisi akhir
Tekan putar: garis menunjukkan pertumbuhan biaya selama pengurutan
Tekan putar atau jalankan langkah demi langkah.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih daftar yang hampir terurut. Setelah satu putaran tanpa pertukaran, algoritma berhenti lebih awal.
Cara kerjanya
Algoritma ini membandingkan dua nilai bersebelahan dan menukarnya jika yang kiri lebih besar. Jadi di tiap putaran, nilai terbesar bergerak terus ke kanan, seperti gelembung yang naik. Jika satu putaran tidak menukar apa pun, daftar sudah terurut.
Kapan ini pilihan yang tepat
Hampir tidak pernah dipakai di program sungguhan, karena lambat untuk daftar yang panjang. Tapi bagus untuk belajar: ia menunjukkan ide dasar mengurutkan dengan membandingkan dan menukar. Ia cepat hanya jika daftar sudah terurut.