Perbandingan
Penukaran
Putaran

  • Dibandingkan
  • Ditukar
  • Di tempatnya

Info lebih lanjut tentang bubble sort

Bubble sort

Bubble sort menyusuri daftar berulang kali, membandingkan setiap pasangan bertetangga, dan menukarnya jika yang kiri lebih besar. Setelah setiap putaran, nilai terbesar yang belum di tempatnya sudah menggelembung ke akhir. Putar pengurutan dengan kecepatan apa pun, atau ikuti satu perbandingan setiap kali, dan amati penghitung perbandingan, penukaran, dan putaran. Tekan Putar untuk melihat pengurutan, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Kotak-kotak menghitung perbandingan, penukaran, dan putaran. Pilih jumlah batang, urutan awalnya, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih jumlah batang dan urutan awalnya: acak, hampir terurut, terbalik, atau dengan sedikit nilai unik. Atau ketik angka sendiri.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja.
  3. Amati kotak-kotak yang menghitung perbandingan, penukaran, dan putaran, lalu bandingkan dengan kasus terburuk.

Cara kerja bubble sort

Mulai dari kiri. Bandingkan dua nilai pertama; jika yang kiri lebih besar, tukar keduanya. Geser satu tempat ke kanan dan bandingkan lagi, sampai akhir daftar. Itu satu putaran, dan hasilnya nilai terbesar ada di tempat terakhir. Putaran berikutnya berhenti satu tempat lebih awal. Ulangi sampai satu putaran tidak melakukan penukaran, atau sampai hanya tersisa satu nilai.

Menghitung kerjanya

Untuk n nilai, putaran pertama melakukan n − 1 perbandingan, berikutnya n − 2, dan seterusnya, jadi pengurutan penuh melakukan paling banyak n(n − 1)/2 perbandingan. Jumlah penukaran selalu sama dengan jumlah inversi pada daftar awal: pasangan nilai yang urutannya salah. Daftar terbalik punya paling banyak, n(n − 1)/2. Daftar terurut tidak punya sama sekali, dan dengan berhenti lebih awal hanya butuh satu putaran berisi n − 1 perbandingan.

Pertanyaan yang sering diajukan

Mengapa disebut bubble sort?

Karena nilai besar naik ke akhir daftar seperti gelembung di air. Di setiap putaran, nilai terbesar yang belum di tempatnya bergerak selangkah demi selangkah ke kanan sampai mencapai tempat akhirnya.

Berapa banyak perbandingan dan penukaran yang dilakukan bubble sort?

Paling banyak n(n − 1)/2 perbandingan untuk n nilai: 45 untuk 10 nilai, 780 untuk 40. Jumlah penukaran selalu sama dengan jumlah inversi pada daftar awal, dari nol untuk daftar terurut sampai n(n − 1)/2 untuk daftar terbalik.

Apa fungsi berhenti lebih awal?

Jika satu putaran penuh tidak melakukan penukaran, setiap pasangan bertetangga sudah berurutan, jadi daftar sudah terurut dan pengurutan bisa berhenti. Jika fitur ini aktif, daftar terurut hanya butuh satu putaran. Jika nonaktif, bubble sort selalu menjalankan semua n − 1 putaran.

Apakah bubble sort dipakai dalam praktik?

Jarang. Algoritma ini sederhana dan stabil, tetapi rata-rata butuh waktu sebanding dengan n². Insertion sort melakukan tugas yang sama dengan langkah lebih sedikit pada daftar kecil atau hampir terurut, dan merge sort atau quicksort jauh lebih cepat pada daftar besar.

Apakah angka saya dikirim ke suatu tempat?

Tidak. Pengurutan berjalan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor