ALGORITMA PENGURUTAN
Bubble Sort
Bubble sort adalah salah satu metode pengurutan exchanging yang bersifat langsung dan termasuk jenis pengurutan yang paling sederhana. Nama bubble sort sendiri berasal dari sifat nilai elemen terbesar yang selalu naik ke atas (ke akhir dari list) seperti gelembung udara(bubble). Ide dari bubble sort adalah sebagai berikut :
1. pengecekan dimulai dari elemen paling awal.
2. Elemen ke-1 dan ke-2 dari list dibandingkan.
3. Jika elemen pertama lebih besar dari elemen kedua, dilakukan pertukaran.
4. Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai elemen terakhir.
5. Bila sudah sampai di elemen terakhir dilakukan pengulangan lagi dari awal sampai tidak ada terjadi lagi pertukaran elemen.
6. Bila tidak ada pertukaran elemen lagi, maka elemen list terurut. Contoh psuedocode untuk algoritma bubble sort dengan urutan membesar :
procedure bubblesort( A : list of integer )
var
temp,i : integer
tukar :boolean
Algoritma
do
tukar := false
for i = 1 to length( A ) – 1 do
if A[ i ] > A[ i + 1 ] then
temp:=A[i]
A[i]:=A[i+1]
A[i+1]:=temp
tukar := true
end if
end for
while tukar
Pada setiap pengulangan (loop) dilakukan pengecekan terhadap tiap elemen mulai elemen pertama dan kedua, elemen kedua dan ketiga,
dan seterusnya sampai elemen sebelum terakhir. Bila masih terjadi pertukaran (tukar = true) dilakukan pengecekan lagi sampai tidak terjadi pertukaran (tukar = false) yang berarti semua elemen dalam list tersebut sudah terurut membesar.
Contoh:
5 3 8 7 9 1 awal (belum terurut )
3 5 7 8 1 9 pengulangan ke-1
3 5 7 1 8 9 pengulangan ke-2
3 5 1 7 8 9 pengulangan ke-3
3 1 5 7 8 9 pengulangan ke-4
1 3 5 7 8 9 pengulangan ke-5 (terurut)
Salah satu kelebihan algoritma bubble sort, terjadi saat semua elemen sudah terurut (kompleksitas = O(n) ) di mana hanya terjadi pengecekan pada setiap elemen, sehingga penelusuran hanya dilakukan satu kali saja. Ini merupakan kasus terbaik yang mungkin terjadi pada algoritma ini. Kelebihan lain dari algoritma ini adalah dapat dieksekusi dan dijalankan dengan cukup cepatdan efisien untuk sebuah kasus yang hanya mengurutkan list yang urutannya sudah hampir benar.Selain kasus terbaik tersebut, kompleksitas untuk algoritma ini akan menjadi O(n²). Karenanya algoritma ini sangat tidak efisien untuk dipergunakan dalam dunia pemrograman yang sesungguhnya, apalagi jika pengurutan dilakukan terhadap elemen yang berjumlah sangat besar. Kelebihan lain bubble sort adalah kemudahan untuk dimengerti. Umumnya algoritma ini sering digunakan untuk mengenalkan algoritma pengurutan dalam dunia komputer karena kesederhanaan idenya. Namun Owen Astrachan,seorang peneliti, mengutarakan sebaiknya algoritma bubble sort ini tidak diajarkan lagi di dunia komputer// Posisi setiap elemen pada bubble sort akan sangat menentukan performa saat eksekusi. Bila
elemen yang terbesar disimpan di awal, maka tidak akan menimbulkan persoalan sebab elemen tersebut secara cepat akan ditukar langsung ke
elemen paling terakhir. Sebaliknya jika elemen terkecil disimpan di bagian paling akhir elemen, maka akan mengakibatkan elemen tersebut akan bergerak sebanyak hanya satu pergeseran setiap masuk ke loop. Ini berarti harus dilakukan pengecekan sebanyak n kali dalam satu loop dan loop akan dijalankan sebanyak n kali juga. Kedua jenis ini biasa disebut rabbit dan turtle. Untuk menghilangkan masalah rabbit dan turtle ini, algoritma ini dikembangkan dengan menciptakan algoritma cocktail sort dan comb sort. Cocktail sort cukup baik untuk mengatasi
permasalahan ini namun untuk kasus terburuk kompleksitasnya sama dengan bubble sort yaitu O(n²). Comb sort cukup baik untuk mempercepat turtle pada elemen list dan juga memiliki kompleksitas yang cukup baik, yaitu n log n, namun comb sort pun memiliki kelemahan, yaitu tidak stabil pada saat pengurutan. Kedua algoritma di atas tidak akan dibahas pada makalah ini. Kelemahan yang lain adalah bubble sort
berinteraksi dengan buruk pada computer modern saat ini. Penulisanya menghabiskan tempat dua kali lebih banyak dari insertion sort dan juga sering melakukan cache misses dan lebih banyak terjadi branch missprediction. Penelitian yang dilakukan oleh Astrachan pada pengurutan string di java juga membuktikan bahwa bubble sort lima kali lebih lambat dari insertion sort. Karenanya pada implementasinya bubble sort jarang digunakan, meskipun banyak juga algoritma lain yang dikembangkan dari bubble sort ini. Dari analisis tersebut, algoritma ini sebaiknya tidak diimplementasikan sebab termasuk tidak efisien penggunaannya, hanya baik digunakan untuk mengurutkan list yang sudah hampir terurut. Selain itu pengurutan jenis ini sangat tidak efisien dan memakan banyak waktu saat dieksekusi. Namun karena algoritma ini termasuk sederhana membuatnya cukup mudah untuk diajarkan sebagai dasar dari algoritma pengurutan.
