ALGORITMA BUBLE SORT
A. Algoritma Buble Sort
Bubble
Sort adalah salah satu algoritma untuk sorting data, atau kata lainnya
mengurutkan data dari yang terbesar ke yang terkecil atau sebaliknya (Ascending
atau Descending). Bubble sort (metode
gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan
penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa
dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada
perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena
masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
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. Algoritma ini termasuk dalam golongan algoritma comparison sort, karena
menggunakan perbandingan dalam operasi antar elemennya. Berikut ini adalah
gambaran dari algoritma bubble sort. Misalkan
kita mempunyai sebuah array dengan
elemen elemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma
bubble sort adalah sebagai berikut.
Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Dapat
dilihat pada proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma
tetap dilanjutkan hingga pass kedua
berakhir. Pass ketiga dilakukan
karena definisi terurut dalam algoritma bubble
sort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass
ketiga dibutuhkan untuk memverifikasi keurutan array tersebut.
B.
Algoritma Bubble Sort
1.
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
algoritme 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).
2.
Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan
pembandingan ini sampai data terakhir. Contoh: 1 dgn 2; 2 dgn 3; 3 dgn 4; 4 dgn
5 … ; n-1 dgn n.
3.
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 dgn
data ke-2, dst.
4.
Proses akan berhenti jika tidak ada pertukaran dalam satu
iterasi.
C.
Kura-kura
dan Kelinci pada Bubble Sort
Dalam
algoritma bubble sort ini, terdapat
beberapa ciri khas yang cukup menonjol, Ciri khas dari algoritma bubble sort ini adalah cepatnya
elemen-elemen besar menempati posisi yang tepat dan lambatnya elemenelemen yang
lebih kecil dalam menempati posisi yang tepat. Hal ini dapat ditunjukkan pada
contoh data “9 2 4 1” yang akan diurutkan berikut ini menggunakan algoritma bubble sort.
Pass Pertama
(9 2 4 1) menjadi (2 9 4 1)
(2 9 4 1) menjadi (2 4 9 1)
(2 4 9 1) menjadi (2 4 1 9)
Pass Kedua
(2 4 1 9) menjadi (2 4 1 9)
(2 4 1 9) menjadi (2 1 4 9)
(2 1 4 9) menjadi (2 1 4 9)
Pass Ketiga
(2 1 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
Pass Keempat
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
(1 2 4 9) menjadi (1 2 4 9)
Dari
proses pengurutan di atas, dapat dilihat bahwa elemen terbesar, “9”, langsung
menempati posisi akhir pada pass pertama. Akan tetapi elemen terkecil, “1”,
baru menempati posisi pertama pada pass keempat, yaitu pass yang terakhir. Oleh
karena itu, muncullah istilah “kura-kura” dan “kelinci” dalam algoritma bubble sort. Pada contoh di atas, “1”
berperan sebagai “kura-kura”, sedangkan “9” berperan sebagai “kelinci”. Fenomena
“kura-kura dan kelinci” ini sering kali mengakibatkan proses pengurutan menjadi
lama, terutama elemen “kura-kura”. Hal ini disebabkan oleh “kura-kura” membutuhkan
satu kali pass hanya untuk bergeser
posisi ke sebelah kiri.
D.
Worst Case
Dalam kasus ini, data terkecil berada pada
ujung array. Contoh Worst-Case dapat dilihat pada pengurutan data “4 3 2
1” di bawah ini.
Pass
Pertama
(4 3
2 1) menjadi (3 4 2 1)
(3 4
2 1) menjadi (3 2 4 1)
(3 2 4
1) menjadi (3 2 1 4)
Pass
Kedua
(3 2
1 4) menjadi (2 3 1 4)
(2 3
1 4) menjadi (2 1 3 4)
(2 1 3
4) menjadi (2 1 3 4)
Pass
Ketiga
(2 1
3 4) menjadi (1 2 3 4)
(1 2
3 4) menjadi (1 2 3 4)
(1 2 3
4) menjadi (1 2 3 4)
Pass
Keempat
(1 2
3 4) menjadi (1 2 3 4)
(1 2
3 4) menjadi (1 2 3 4)
(1 2 3
4) menjadi (1 2 3 4)
Dari
langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu pass, data terkecil akan bergeser ke
arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil
dari urutan keempat menuju urutan pertama, dibutuhkan pass sebanyak tiga kali, ditambah satu kali pass untuk
memverifikasi. Sehingga jumlah proses pada kondisi best case dapat dirumuskan sebagai berikut.
Jumlah proses = n2 + n …………………………………….( 1)
Dalam
persamaan (1) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga
notasi Big-O yang didapat adalah O(n2). Dengan kata lain, pada
kondisi worst-case, algoritma bubble sort termasuk dalam kategori
algoritma kuadratik.
Best case
Dalam
kasus ini, data yang akan disorting telah terurut sebelumnya, sehingga proses
perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali pass. Proses perbandingan dilakukan
hanya untuk memverifikasi keurutan data. Contoh Best-Case dapat dilihat pada pengurutan data “1 2 3 4” di bawah
ini.
Pass Pertama
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dari
proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi satu
kalipun, sehingga tidak dilakukan pass selanjutnya. Perbandingan elemen
dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya
dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini
adalah O(n). Dengan kata lain, pada kondisi Best-Case
algoritma bubble sort termasuk pada
algoritma lanjar.
Average Case
Pada kondisi average-case, jumlah pass
ditentukan dari elemen mana yang mengalami penggeseran ke kiri paling banyak.
Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan
saja (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses
penggeseran paling banyak adalah elemen 2, yaitu sebanyak dua kali.
Pass
Pertama
(1 8
6 2) menjadi (1 8 6 2)
(1 8
6 2) menjadi (1 6 8 2)
(1 6 8
2) menjadi (1 6 2 8)
Pass
Kedua
(1 6
2 8) menjadi (1 6 2 8)
(1 6
2 8) menjadi (1 2 6 8)
(1 2 6
8) menjadi (1 2 6 8)
Pass
Ketiga
(1 2
6 8) menjadi (1 2 6 8)
(1 2
6 8) menjadi (1 2 6 8)
(1 2 6
8) menjadi (1 2 6 8)
Dari
proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan diperlukan dua
buah passing, ditambah satu buah passing untuk memverifikasi. Dengan kata lain,
jumlah proses perbandingan dapat dihitung sebagai berikut.
Jumlah proses = x2 + x ………………………………(2)
Dalam
persamaan (2) di atas, x adalah jumlah penggeseran terbanyak. Dalam hal ini, x
tidak pernah lebih besar dari n, sehingga x dapat dirumuskan sebagai persamaan (1) dan (2) di atas, dapat
disimpulkan bahwa notasi big-O nya adalah O(n2). Dengan kata lain, pada
kondisi average case algoritma bubble sort termasuk dalam algoritma
kuadratik.
Kelebihan
Bubble Sort
Beberapa
kelebihan dari algoritma bubble sort
adalah sebagai berikut :
·
Algoritma yang simpel.
·
Mudah untuk diubah menjadi kode.
·
Definisi terurut terdapat dengan jelas dalam
algoritma.
·
Cocok untuk pengurutan data dengan elemen kecil
telah terurut.
Algoritma
yang simpel. Hal ini dilihat dari proses pengurutan yang hanya menggunakan
rekurens dan perbandingan, tanpa penggunaan
proses lain. Algoritma pengurutan lain cenderung menggunakan proses lain, misalnya
proses partisi pada algoritma quick sort.
Mudah untuk diubah menjadi kode. Hal ini diakibatkan oleh simpelnya algoritma bubble sort, sehingga kecil kemungkinan
terjadi kesalahan syntax dalam
pembuata kode. Definisi terurut terdapat dengan jelas dalam algoritma. Definisi
terurut ini adalah tidak adanya satu kalipun swap pada satu kali pass.
Berbeda dengan algoritma lain yang seringkali tidak memiliki definisi terurut
yang jelas tertera pada algoritmanya, misalnya quick sort yang hanya melakukan partisi hingga hanya ada dua buah
nilai yang bisa dibandingkan. Cocok untuk pengurutan data dengan elemen kecil
telah terurut. Algoritma bubble sort
memiliki kondisi best case dengan
kompleksitas algoritma O(n).
Kekurangan
Bubble Sort
Beberapa
kekurangan dari algoritma bubble sort
adalah sebagai berikut :
·
Tidak efektif dalam pengurutan data berskala besar.
·
Langkah pengurutan yang terlalu panjang.
Kekurangan
terbesar dari bubble sort adalah kompleksitas
algoritma yang terlalu besar, baik dalam average
case maupun worst case, yaitu O(n2),
sehingga seringkali disebut sebagai algoritma primitif, brute-force, maupun algoritma naïf. Untuk 1000 buah data misalnya,
maka akan terjadi proses tidak lebih dari satu juta proses perbandingan. Kompleksitas
yang besar ini juga seringkali membuat algoritma bubble sort sebagai “the
general bad algorithm”. Bahkan, diantara algoritma pengurutan lain yang memiliki
kompleksitas algoritma O(n2), insertion
sort cenderung lebih efisien.
Contoh
Perhitungan Manual
Terdapat
deret array [ 20, 5, 9, 2, 4, 11, 22 ], Selesaikan deret array tersebut dengan
menggunakan penyelesaian metode bubble sort.
Jawab :
Pass Pertama
(20 5 9 2
4 11 22) menjadi (5 20 9 2
4 11 22)
(5 20 9 2 4
11 22) menjadi (5 9 20 2
4 11 22)
(5 9 20 2 4 11 22) menjadi (5 9 2 20 4 11 22)
(5 9 2 20 4 11 22) menjadi (5 9 2 4 20 11 22)
(5 9 2 4 20 11 22)
menjadi (5 9 2 4 11 20 22)
(5 9 2 4 11 20 22) menjadi (5 9 2 4 11 20 22)
Pass
Kedua
(5 9 2 4 11 20 22) menjadi (5 9 2 4 11 20 22)
(5 9 2 4 11 20 22) menjadi (5 2 9 4 11 20 22)
(5 2 9 4 11 20 22)
menjadi (5 2 4 9 11 20 22)
(5 2 4 9 11 20 22) menjadi (5 2 4 9 11 20 22)
(5 2 4 9 11
20 22) menjadi (5 2 4 9 11
20 22)
(5 2 4 9 11 20 22) menjadi (5 2 4 9 11 20 22)
Pass
Ketiga
(5 2 4 9 11 20 22) menjadi (2 5 4 9 11 20 22)
(2 5
4 9 11 20 22) menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22)
menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22)
menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22 ) menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22) menjadi (2 4 5 9 11 20 22)
Pass
Keempat
(2 4 5 9 11 20 22) menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22) menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22)
menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22)
menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22)
menjadi (2 4 5 9 11 20 22)
(2 4 5 9 11 20 22) menjadi (2 4 5 9 11 20 22)
Pass keempat dibutuhkan untuk
memverifikasi keurutan array
tersebut.
DAFTAR PUSTAKA
Erzandi, Muhammad O. 2007. Algoritma
Pengurutan dalam pemrograman.Bandung : ITB.
Rheinaldi, Riyan (2017), Analisis
Algoritma Buble Sort, Jurnal, Teknik Informatika, Institute
Teknologi Bandung , Bandung.
Komentar
Posting Komentar