Ide dari algoritma ini sangat menarik. Setiap pasangan
data: x[j] dengan x[j-1], untuk semua i=1,...,n-1 harus
memenuhi keterurutan, yaitu x[j] > x[j-1]. Apabila
tidak memenuhi maka posisi kedua data harus ditukar.
Untuk pemrograman konvensional maka pemeriksaanpemeriksaan
pasangan tersebut harus dilakukan satu
demi satu, misalnya oleh bubble-sort dilakukan dari
kanan ke kiri serta di dalam sejumlah iterasi.
Pada iterasi ke-i, pemeriksaan tsb. dilakukan pula
dalam Loop-for sbb:
for (j=n-1; j > i; j--) {
if (x[j] < x[j-1]) {
tmp = x[j];
x[j] = x[j-1];
x[j-1] = tmp;
}}
Loop-for tersebut akan menggeser bilangan terkecil ke
posisi i. Loop-for dilakukan hanya sampai ke i karena
pada iterasi ke-i data dalam x[0], x[1], ..., x[i-1]
merupakan yang paling kecil dan sudah terurut hasil
pengeseran yang dilakukan setiap loop sebelumnya.
Oleh sebab itu iterasi hanya dilakukan untuk harga
i=0, 1, ..., n-2 atau sampai tidak terjadi penukaran
dalam suatu iterasi.
void BubbleSort() {
ch = true;
for (i=0; i < n-2 && ch; i++) {
ch = false;
for (j=n-1; j > i; j--) {
if (x[j] < x[j-1]) {
tmp = x[j];
x[j] = x[j-1];
x[j-1] = tmp;
ch = true;
}}}}
Contoh untuk mengurutkan data
34,43,65,90,48,82,93,86,26,76,49,23,56,37.
Pada iterasi i=0:
j=13: tukar 56-37 menjadi
34,43,65,90,49,82,93,86,26,76,49,23,37,56
j=12: tidak ada penukaran
j=11: tukar 49-23 menjadi
34,43,65,90,48,82,93,86,26,76,23,49,37,56
j=10: tukar 76-23 menjadi
34,43,65,90,48,82,93,86,26,23,76,49,37,56
j= 9: tukar 26-23 menjadi
34,43,65,90,48,82,93,86,23,26,76,49,37,56
j= 8: tukar 86-23 menjadi
34,43,65,90,48,82,93,23,86,26,76,49,37,56
j= 7: tukar 93-23 menjadi
34,43,65,90,48,82,23,93,86,26,76,49,37,56
j= 6: tukar 82-23 menjadi
34,43,65,90,48,23,82,93,86,26,76,49,37,56
j= 5: tukar 49-23 menjadi
34,43,65,90,23,48,82,93,86,26,76,49,37,56
j= 4: tukar 90-23 menjadi
34,43,65,23,90,48,82,93,86,26,76,49,37,56
j= 3: tukar 65-23 menjadi
34,43,23,65,90,48,82,93,86,26,76,49,37,56
j= 2: tukar 43-23 menjadi
34,23,43,65,90,48,82,93,86,26,76,49,37,56
j= 1: tukar 34-23 menjadi
23,34,43,65,90,48,82,93,86,26,76,49,37,56
Pada iterasi i=1:
j=13: tidak ada penukaran
j=12: tukar 49-37 menjadi
23,34,43,65,90,48,82,93,86,26,76,37,49,56
j=11: tukar 76-37 menjadi
23,34,43,65,90,48,82,93,86,26,37,76,49,56
j=10: tidak ada penukaran
j= 9: tukar 86-26 menjadi
23,34,43,65,90,48,82,93,26,86,37,76,49,56
j= 8: tukar 93-26 menjadi
23,34,43,65,90,48,82,26,93,86,37,76,49,56
j= 7: tukar 82-26 menjadi
23,34,43,65,90,48,26,82,93,86,37,76,49,56
...
j= 2: tukar 34-26 menjadi
23,26,34,43,65,90,48,82,93,86,37,76,49,56
Dan seterusnya. Hingga, pada setiap akhir iterasi
berikutnya berturut-turut menjadi:
i=2: 23,26,34,37,43,65,90,48,82,93,86,49,76,56
i=3: 23,26,34,37,43,48,65,90,49,82,93,86,56,76
i=4: 23,26,34,37,43,48,49,65,90,56,82,93,86,76
i=5: 23,26,34,37,43,48,49,56,65,90,76,82,93,86
i=6: 23,26,34,37,43,48,49,56,65,76,90,82,86,93
i=7: 23,26,34,37,43,48,49,56,65,76,82,90,86,93
i=8: 23,26,34,37,43,48,49,56,65,76,82,86,90,93
i=9: 23,26,34,37,43,48,49,56,65,76,82,86,90,93
Dari kedua iterasi dengan increment linear demikian
dapat mudah dilihat bahwa algoritma ini memiliki
kompleksitas O(n2) dan proses akan menjadi amat
cepat kalau data sudah sebagian besar terurut. Masalah
yang dihadapi algoritma ini adalah banyaknya
penukaran yang dilakukan selama proses dalam
kondisi normal. Efisiensi dapat ditingkatkan dengan
mengurangi proses penukaran dengan penggeseran
dan penyisipan seperti halnya insertion sort. Untuk
lingkungan pemrograman paralel dengan array
processor pengurutan ini menjadi amat menarik untuk
dikaji.
Jika Bubble Sort dalam setiap iterasi melakukan loopfor
penukaran ke satu arah, Shaker Sort (suatu variant
dari Bubble Sort) melakukan loop-for penukaran
dengan arah bolak-balik dengan batas loop-for kiri
dan kanan semakin menyempit.
Untuk bubble sort, best case dari Big-O ( O ) adalah
O(n), dimana n adalah jumlah datanya. Best case
terjadi bila data yang hendak disorting sudah terurut,
misal jika ada 1500 data dan semuanya sudah terurut
maka algoritma Bubble Sort tersebut hanya
melewatinya satu kali yaitu O(1500).
Akan tetapi, worst case nya adalah O(n2), worst case
terjadi apabila datanya betul-betul sangat tidak terurut,
bayangkan bila ada 20 data, pada worst case
komputasi yang dilakukan = O(202) = O(4000) ->
Lebih besar dibanding 1500 data pada kondisi best
case!
dikutip dari makalah Rio Cahya Dwiyanto
Jurusan Teknik Informatika ITB, Bandung, email: kasrut_desu@yahoo.co.id
