Bubble Sort adalah suatu algoritma pengurutan data dengan cara membandingkan data satu-persatu secara urut dari yang terkecil ke terbesar. Metode pengurutan gelembung (Bubble Sort) diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada pengurutan gelembung.
Algoritma bubble sort adalah salah satu algoritma pengurutan yang paling simple, baik dalam hal pengertian maupun penerapannya. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi.
Contoh pengurutan dengan metode buble sort. Misal kita mempunyai larik (array) dengan 5 elemen data yaitu 5,6,4,3,7. Maka langkah-langkah pengurutan dengan metode buble sort adalah sebagai berikut.
Itterasi 1 :
5 6 4 3 7 menjadi 5 6 4 3 7
5 6 4 3 7 menjadi 5 4 6 3 7
5 4 6 3 7 menjadi 5 4 3 6 7
5 4 3 6 7 menjadi 5 4 3 6 7
Itterasi 2
5 4 3 6 7 menjadi 4 5 3 6 7
4 5 3 6 7 menjadi 4 3 5 6 7
4 3 5 6 7 menjadi 4 3 5 6 7
4 3 5 6 7 menjadi 4 3 5 6 7
Itterasi 3
4 3 5 6 7 menjadi 3 4 5 6 7
3 4 5 6 7 menjadi 3 4 5 6 7
3 4 5 6 7 menjadi 3 4 5 6 7
3 4 5 6 7 menjadi 3 4 5 6 7
Dapat dilihat pada proses di atas, sebenarnya pada itterasi ketiga, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga itterasi ketiga berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubblesort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.
Algoritma Buble Sort
- Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritma menghasilkan data dengan urutan ascending (A-Z) kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z).
- Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dengan 2; 2 dengan 3; 3 dengan 4; 4 dengan 5 … ; n-1 dengan n.
- Selesai satu iterasi, adalah jika kita sudah selesai membandingkan antara (n-1) dgn n. Setelah selesai satu iterasi kita lanjutkan lagi iterasi berikutnya sesuai dengan aturan ke-1. mulai dari data ke-1 dengan data ke-2, dst.
- Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.
Source Code Buble Sort dalam PHP
<!DOCTYPE html><html> <head> <title>Sorting3</title> </head> <body> <h3 style="text-decoration:underline";>Bubble Sort</h3> <?php define ("n", 9); $m = array(10,13,4,20,18,2,30,8,25); echo "<h3>Sebelum Diurutkan</h1>"; for ($y=0; $y <= n-1; $y++) echo "$m[$y] "; $z=0; while($z<=n-2) { $y=0; while($y<=n-2 - $z) { if ($m[$y] > $m[$y+1]) { $o = $m[$y]; $m[$y] = $m[$y+1]; $m[$y+1] = $o; } $y++; } $z++; } echo "<h3>Sesudah Diurutkan</h3>"; for ($y=0; $y<= n-1; $y++) echo "$m[$y] "; ?> </body> </html>
No comments:
Post a Comment