Bubble Sort Part 2: Turtle & Rabbit

Dari posting sebelumnya, kita udah tau ada yang namanya bubble sort, bahkan udah ada program yang bisa di-run segala. Sekarang, kita bakal bahas tentang 2 hal di bubble sort yang menjadi pemikiran para ahli di bidang algoritma pengurutan. 2 hal tersebut yaitu rabbit dan turtle. Apakah kedua hal itu?

Rabbit adalah nilai tinggi yang ada di ujung daftar (sebelah kiri) dari daftar nilai yang akan diurutkan secara menaik. Sedangkan turtle adalah sebaliknya, nilai rendah yang ada di ujung daftar (sebelah kanan) dari daftar nilai yang akan diurutkan menaik.

Rabbit akan lebih cepat untuk diurutkan, sedangkan turtle akan menyebabkan jalannya lama eksekusi dari program pengurutan.

Gimana?! Bisa dimengerti kah? Kalau kamu belum ada bayangan, di sini bisa dilihat contohnya kok. Pertama.. rabbit dulu ya… Rabbit, sesuai definisinya, nilai besar yang ada di ujung sebelah kiri dari daftar yang akan diurutkan menaik. Jadi, contoh valid daftarnya adalah “13 2 4 7 9”. Nilai 13 adalah rabbit. Dan kenapa dia disebut rabbit?! Kita lihat langkah2 pengurutannya:

Kondisi awal: 9 2 4 7 8

First Pass
9 2 4 7 8 --> 2 9 4 7 8 (swapped terjadi)
2 9 4 7 8 --> 2 4 9 7 8 (swapped terjadi)
2 4 9 7 8 --> 2 4 7 9 8 (swapped terjadi)
2 4 7 9 8 --> 2 4 7 8 9 (swapped terjadi)

dikarenakan terjadinya swapped,
maka perbandingan dimulai dari elemen ke-0 sampai ke-(n-1) diulang.

Second Pass
2 4 7 8 9 --> 2 4 7 8 9 (swapped tidak terjadi)
2 4 7 8 9 --> 2 4 7 8 9 (swapped tidak terjadi)
2 4 7 8 9 --> 2 4 7 8 9 (swapped tidak terjadi)
2 4 7 8 9 --> 2 4 7 8 9 (swapped tidak terjadi)

Perulangan berhenti karena swapped tidak terjadi.
Kondisi akhir: daftar terurut menaik.

Lihat kan kenapa dia disebut dengan rabbit?! Cuma butuh 2 pass aja untuk mengurutkan nilainya. Bandingkan dengan turtle berikut. Anggap kita punya daftar nilai 2 4 7 9 1. Nilai 1 adalah turtle karena merupakan nilai kecil yang ada di sebelah kanan daftar yang akan diurutkan menaik:

Kondisi awal: 2 4 7 9 1

First Pass
2 4 7 9 1 --> 2 4 7 9 1 (swapped tidak terjadi)
2 4 7 9 1 --> 2 4 7 9 1 (swapped tidak terjadi)
2 4 7 9 1 --> 2 4 7 9 1 (swapped tidak terjadi)
2 4 7 9 1 --> 2 4 7 1 9 (swapped terjadi)

Second Pass
2 4 7 1 9 --> 2 4 7 1 9 (swapped tidak terjadi)
2 4 7 1 9 --> 2 4 7 1 9 (swapped tidak terjadi)
2 4 7 1 9 --> 2 4 1 7 9 (swapped terjadi)
2 4 1 7 9 --> 2 4 1 7 9 (swapped tidak terjadi)

Third Pass
2 4 1 7 9 --> 2 4 1 7 9 (swapped tidak terjadi)
2 4 1 7 9 --> 2 1 4 7 9 (swapped terjadi)
2 1 4 7 9 --> 2 1 4 7 9 (swapped tidak terjadi)
2 1 4 7 9 --> 2 1 4 7 9 (swapped tidak terjadi)

Fourth Pass
2 1 4 7 9 --> 1 2 4 7 9 (swapped terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)

Fifth Pass
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)
1 2 4 7 9 --> 1 2 4 7 9 (swapped tidak terjadi)

Algoritma berhenti. Kondisi akhir: daftar terurut menaik.

Lihat kan?! Perbandingannya, dengan jumlah data yang sama… rabbit cuma butuh 2 pass, sedangkan turtle butuh 5 pass. Makanya namanya rabbit & turtle. Kelinci yang cepat, dan kura-kura yang lambat. Kata para peneliti, hal ini dikarenakan perbandingan dari bubble sort dilakukan kepada nilai yang tepat berada di sampingnya. Seandainya, perbandingan dilakukan dalam jarak tertentu, kemungkinan hal ini bisa diatasi menjadi lebih baik. Dan hal ini memunculkan algoritma lain, yaitu comb sort.

Well.. untuk hal ini, kita teruskan di tulisan berikutnya aja yah…

One thought on “Bubble Sort Part 2: Turtle & Rabbit

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s