Lanjut50 XPUnit 10: Pencarian dan Pengurutan, soal 6 dari 10
Hitung Tukar Bubble Sort
Hitung berapa kali bubble sort menukar elemen.
Bubble sort terkenal lambat. Seberapa lambat tergantung datanya: data yang hampir terurut cukup sedikit pertukaran, data yang terbalik butuh sangat banyak. Hitung banyaknya pertukaran itu.
Masukan
Baris pertama berisi N (1 sampai 1000). Baris kedua berisi N bilangan bulat.
Keluaran
Banyaknya pertukaran yang dilakukan bubble sort untuk mengurutkan data dari kecil ke besar. Dua elemen yang sama tidak ditukar.
Contoh masukan dan keluaran
Contoh 1
Masukan
5 3 1 4 1 5
Keluaran
3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Jalankan bubble sort apa adanya dan tambahkan penghitung setiap kali terjadi pertukaran.
Petunjuk 2
Banyaknya pertukaran sama dengan banyaknya pasangan yang urutannya terbalik, yaitu posisi i < j dengan data[i] > data[j].