ALGORITMA BRUTE FORCE

Pertemuan 3

Definisi

• Brute force adalah sebuah pendekatan yang lempang untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.

• Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas.

Karakteristik AlgoritmaBrute Force

• Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naiv

• Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih cerdas dan lebih mangkus.

• Untuk masalah yang ukurannya kecil, kesederhanaan brute force biasanya lebih diperhitungkan daripada ketidakmangkusannya.

• Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus.

• Algoritma brute force seringkali lebih mudah diimplementasikan daripada algoritma yang lebih canggih, dan karena kesederhanaannya, kadang-kadang algoritma brute force dapat lebih mangkus (ditinjau dari segi implementasi).

Konsep Bubble Sort / metode gelembung

• Metode/algoritma pengurutan 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.

Algoritma Bubble Sort procedure BubbleSort (input/output L : TabelInt, input n : integer) { Mengurutkan tabel L[1..N] sehingga terurut menaik dengan metode pengurutan bubble sort.

Masukan : Tabel L yang sudah terdefenisi nilai-nilainya. Keluaran: Tabel L yang terurut menaik sedemikian sehingga L[1] L[2] … L[N]. } 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

Algoritma Bubble Sort

• 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).

• Membandingkan data ke-(i+1) dengan data ke-(i+2). • 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.

• Proses akan berhenti jika tidak ada pertukaran dalam satu iterasi.

Contoh• Misalkan data : 6, 4, 3, 2 dan ingin mengurutkan data ini

(ascending) dengan menggunakan bubble sort.

Berikut ini adalah proses yang terjadi:

• Iterasi ke-1: 4, 6, 3, 2 :: 4, 3, 6, 2 :: 4, 3, 2, 6

(ada 3 pertukaran)

• Iterasi ke-2: 3, 4, 2, 6 :: 3, 2, 4, 6 :: 3, 2, 4, 6

(ada 2 pertukaran)

• Iterasi ke-3: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6

(ada 1 pertukaran)

• Iterasi ke-4: 2, 3, 4, 6 :: 2, 3, 4, 6 :: 2, 3, 4, 6

(ada 0 pertukaran) -> proses selesai

Analisis Algoritma Bubble Sort

• Kondisi Average-CaseJumlah pass ditentukan dari elemen mana yang mengalami

penggeseran ke kiri paling banyak.

Kekuatan dan Kelemahan Metode Brute Force

• Kekuatan: Metode brute force dapat digunakan untuk memecahkan

hampir sebagian besar masalah.

Metode brute force sederhana dan mudah dimengerti.

Metode brute force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks.

Metode brute force menghasilkan algoritma baku (standard) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).

• Kelemahan: Metode brute force jarang menghasilkan algoritma yang

mangkus.

Beberapa algoritma brute force lambat sehingga tidak dapat diterima.

Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya.

TUGAS

• Insertion Sort