Metode Pengurutan Gelembung

Pengurutan adalah proses mengatur sekumpulan obyek menurut urutan atau susunan tertentu. Urutan obyek tersebut dapat menaik (ascending) atau menurun (descending). Data yang telah terurut memiliki beberapa keuntungan. Selain mempercepat pencarian dari data yang terurut dapat langsung diketahui nilai maksimum dan nilai minimum. Untuk data numerik menurun nilai minum adalah elemen terakhir, dan nilai maksimum adalah elemen pertama.

Asal penamaan “Bubble Sort” diinspirasikan oleh gelembung sabun yang berada di permukaan air. Bubble short adalah metode sorting yang mudah di pahami,bila dibandingkan dengan metode sorting yang lainnya. Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan ini seolah-olah menggeser satu persatu elemen dari kanan ke kiri. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Proses Bubble Sort
Umumunya proses pengurutan Bubble adalah pengurutan dari kanan ke kiri dimana bilangan yang terkecil ada di sebelah kiri dan bilangan terbesar adalah bilangan yang paling kanan. Setiap tahapnya selalu dimulai dari index yang paling kanan dan dibandingkan dengan sebelahnya, apakah dia lebih kecil? Jika iya maka tukarkan, jika tidak cek bilangan yang sebelumnya. Proses-proses dari Bubble sort:

1) Mulai dari elemen K= N, N-1, N-2….sampai K=2, bandingkan L[K] dengan
L[K-1]. Jika L[K]<L[K-1], maka tukarkan L[K] dengan L[K-1].
2) Mulai dari elemen K = N,N-1,…3, bandingkan L[K] dengan L[K-1]. JikaL[K]<L[K-1], tukarkan L[K] dengan L[K-1].
3) Mulai dari elemen K=N,N-1,…4. Bandingakan L[K] dengan L[K-1].Jika L[K]<L[K-1], tukarkan L[K] dengan L[K-1]. Pada akhir langkah 3, elemen L[3] berisi harga minimum ketiga, larik L[1…3] terurut, sedangkan L[4…N] belum terurut.
……..
4) Dan yang terakhir: N-1. Mulai dari elemen K=N, bandingkan L[K] dengan L[K-1]. Jika L[K]<L[K-1], tukarkan L[K] dengan L[K-1].

Contoh proses pengurutan dengan Bubble Sort:

Misal kita mempunyai sebuah array dengan nama L, dengan nilai masing-masing elemen sebagai berikut:
Index 1 2 3 4 5
Nilai 78 13 67 2 9

Hal pertama yang akan kita lakukan adalah menentukan nilai elemen yang pertama yang harus dibandingkan (K) karena pengurutan bubble memulai dari kanan ke kiri maka nilai K adalah index yang paling kanan yaitu 5.

Indek 1:

K=5:
Kita akan membandingkan L[5] dengan L[4], karena L[5]!<L[4] maka tidak terjadi pertukaran.
78 13 67 2 9

K=4:
Bandingkan L[4] denganL [3], karenaL[4]<L[3]. Maka tukarkan L[4] denganL[3].

78 13 2 67 9
78 13 67 2 9

K=3:
Bandingkan L[3] dengan L[2], karena L[3]<L[2], maka tukarkan L[3] dengan L[2].
78 2 13 67 9

78 13 2 67 9


K=2:
Bandingkan kembali L[2] dengan L[1], karena L[2]<L[1] maka tukarkan L[2] dengan L[1].
78 2 13 67 9
2 78 13 67 9


Karena K hanya sampai i+1 maka nilai K pada tahap ini hanya sampai K=2.
Dan hasil akhir dari tahapan ini adalah:
2 78 13 67 9

Indek 2:
K=5

Seperti indeks 1 kita akan membandingkan L[5] denganL[4]. Kerena L[5]<L[4] maka L[5] ditukarkan dengan L[4].
2 78 13 67 9
2 78 13 9 67


K=4
Selanjutnya kita bandingkan lagi L[4] dengan [3].Karena L[4]<L[3] maka tukarkan nilai L[4] dengan nilai L[3].
2 78 13 9 67
2 78 9 13 67


K=3:
Bandingkan kembali L[3] dengan L[2], karena L[3]<L[2] maka tukarkan L[3] dengan L[2].
2 9 78 13 67
2 78 9 13 67

Tahap 4

2 9 78 13 67

K=5:
Bandingkan L[5] dengan L[4], karena L[5]!<L[4] maka tidak terjadi pertukaran.
2 9 78 13 67

K=4:
Bandingkan kembali L[4] dengan L[3], karena L[4]<L[3] maka tukarkan L[4] dengan L[3].
2 9 78 13 67
2 9 13 78 67

Hasil dari tahap ini adalah:
2 9 13 78 67

Indeks 4

K=5
Pada indeks 4 ini kita hanya bisa membandingkan L[5] dengan L[4]. Karena L[5]<L[4] maka tukarkan L[5] dengan L[4].
2 9 13 67 78

2 9 13 78 67

Hasil pengurutan adalah:
2 9 13 67 78

Kesimpulan
Pengurutan Bubble Sort merupakan pengurutan yang tidak efisien, karena membutuhkan operasi pertukaran pada setiap langkah. Sehingga jika ukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang relatif lebih lama dibandingkan dengan metode pengurutan yang lain sehingga tidak direkomendasikan untuk dipakai, anmun metode ini cukup sederhana untuk dipahami.
procedure UrutGelembung(input/output L: Larik; input N : integer)
Deklarasi:
I : integer {pencacah untuk jumlah langkah}
K : integer {pencacah untuk pengapungan pada setiap langkah}
Temp : integer {peubah bantu untuk pertukaran}
Algoritma
for I ← 1 to N-1 do
for K ← N downto I+1 do
if L[K] < L[K-1] then {pertukarkan L[K] dengan L[K-1]}
Temp ← L[K]
L[K] ← L[K-1]
L[K-1] ← Temp
endif
endfor
endfor