Bubble Sort

Salah satu contoh tipe algoritma brute force adalah bubble sort (pengurutan gelembung). Dikatakan demikian karena algoritma ini menggunakan strategi langsung dengan membandingkan semua posisi dan melakukan pertukaran.

Gambar: Tahapan pengurutan data pada  bubble sort

Secara ringkas, algoritma pengurutan bubble sort adalah sebagai berikut:

1. Inisialisasi i = 1 { tahap pertama } 
2. Mulai perbandingan dari posisi elemen terakhir, contoh di atas, jumlah data, n = 7
3. Inisialisasi j ← n { j adalah variabel pencacah yang akan bergerak mundur ke kiri }
4. Jika Data j < Date j-1, pertukarkan
5. j ← j - 1
6. Jika j > i  { j belum mencapai batas paling kiri, garis merah pada tiap tahapan }, maka ulang baris ke 4,  jika tidak, maka lanjutkan ke baris 7
7. i ← i + 1 { perubahan tahapan, batas paling kiri berkurang/bergeser, garis merah }
8. Jika i < n, maka ulang ke baris 3, jika tidak, maka sudah mencapai tahap akhir, n-1.
9. Selesai.

Gambar: Tahapan pengurutan data pada bubble sort

Pada contoh program yang sedang dijalankan dengan jumlah data 7, proses  pengulangan tahapan adalah sebanyak n-1 = 6 dengan jumlah perbandingan (langkah) berkurang seiring posisi tahapan, misal pada tahap ke-1, jumlah langkah perbandingan = 6 dan tahap ke-2, jumlah langkah perbandingan = 5 serta seterusnya (lihat gambar di atas). 

Gambar: Algoritma Bubble Sort dalam bentuk Pseudo Code

Algoritma Bubble Sort adalah algoritma yang tidak mangkus (dari aspek waktu dan penggunaan sumber daya memory) dan menurut penulis merupakan algoritma paling buruk dalam sorting. Kalo kita amati, ada 2 proses yang dilakukan, yaitu: Perbandingan dan Pertukaran sebanyak n-1 faktorial  = (6 x 5 x 4 x 2 x 1). Algoritma ini disempurnakan dengan metode Selection sort karena proses Pertukarannya hanya sebanyak n-1 = 6, meskipun Perbandingannya tetap n-1 faktorial.

Kode: Bahasa C++