Algoritma Sorting

ALGORITMA MARGE SORT

Konsep Algoritma Merge Sort

Secara konseptual, untuk sebuah array berukuran n, Merge Sort bekerja sebagai berikut: 

1. Jika bernilai 0 atau 1, maka array sudah terurut. Sebaliknya: 
2. Bagi array yang tidak terurut menjadi dua subarray, masing-masing berukuran n/2. 
3. Urutkan setiap sub-array. Jika sub-array tidak cukup kecil, lakukan rekursif langkah 2 terhadap sub-array. 
4. Menggabungkan dua sub-array kembali menjadi satu array yang terurut.

Merge sort menggabungkan dua ide utama untuk meningkatkan runtimenya:

1. Array kecil akan mengambil langkah-langkah untuk menyortir lebih sedikit dari array besar. 
2. Lebih sedikit langkah yang diperlukan untuk membangun sebuah array terurut dari dua buah array terurut daripada dari dua buah array tak terurut.

Kompleksitas Merge Sort 

Dalam algoritma ini, jumlah perbandingan yang terjadi bergantung pada h dan m. Kondisi terburuk terjadi ketika perulangan berhenti, karena salah satu indeks, sebut saja i, telah mencapai titik berhentinya dimana indeks lain j telah mencapai m – 1, lebih rendah 1 dari titik berhentinya. Sehingga, W(h,m) = h + m – 1 

Jumlah keseluruhan perbandingan adalah jumlah banyaknya perbandingan dalam pemanggilan rekursif merge sort dimana U sebagai input, banyaknya perbandingan dalam pemanggilan rekursif merge sort dimana V sebagai input, dan banyaknya perbandingan di top-level pemanggilan merge. Sehingga, W(n) = W(h) + W(m) + h + m – 1 

Pertama, kita menganalisa kasus diaman n adalah eksponen dari 2. Dalam kasus ini, Ekspresi untuk W(n) menjadi Ketika besar input adalah 1, kondisi pemberhentian terpenuhi dan tak ada penggabungan. Sehingga, W(1) adalah 0. 

Solusi dari rekurens tersebut adalah Merge Sort akan selalu membagi dua tiap sub-arraynya hingga mencapai basis, sehingga kompleksitas dari algoritma Merge Sort, berlaku untuk semua kasus (Worst Case = Best Case = Average Case).

ALGORITMA BRUTE FORCE 

Konsep Algoritma Brute force 

Secara konseptual, brute force bekerja sebagai berikut: 

1. Mula-mula pattern dicocokkan pada awal teks. 
2. Dengan bergerak dari kiri ke kanan, bandingkan setiap karakter di dalam pattern dengan karakter yang bersesuaian di dalam teks sampai: 
• semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau 
• dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil) 
3. Bila pattern belum ditemukan kecocokannya dan teks belum habis, geser pattern satu karakter ke kanan dan ulangi langkah 2.

Penjelasan• Brute force adalah sebuah pendekatan yang sangat jelas(straightforward) untuk memecahkan suatu persoalan, biasanya didasarkan pada problem statement dan definisi konsep yang dilibatkan. Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas. 

• Contoh algoritma yang menggunakan brute force antara lain : buble sort,     convex hull, closest pair, travelling salesman problem, knapsack, string   matching, dan selection sort.

• Contoh-contoh masalah yang dipecahkan secara brute force:

• Menghitung an (a > 0, n adalah bilangan bulat tak-negatif)

   • an = a × a × … × a (sebanyak n kali) , jika n > 0

   • a=1 , jika n = 0

   • Algoritma: kalikan 1 dengan a sebanyak n kali 

Pseudocode

• function pangkat(input a, n : integer) integer

• { Menghitung an, a > 0 dan n bilangan bulat tak-negatif

• Masukan: a, n

• Keluaran: nilai perpangkatan.

• }

• Deklarasi

• k, hasil : integer

•• Algoritma:

• hasil 1

• for k 1 to n do

• hasil hasil * a

• endfor

• return hasil• 

Cara kerja• Secara konseptual, brute force bekerja sebagai berikut:• Mula-mula pattern dicocokkan pada awal teks.• Dengan bergerak dari kiri ke kanan, bandingkan setiap karakter di dalam pattern dengan karakter yang bersesuaian di dalam teks sampai:• semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau• dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil)• Bila pattern belum ditemukan kecocokannya dan teks belum habis, geser pattern satu karakter ke kanan dan ulangi langkah 2. 

Keunggulan brute force• Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability).• 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 brute force• Metode brute force jarang menghasilkan algoritma yang mangkus.• Beberapa algoritma brute force lambat sehingga tidak dapat diterima.• Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya. 

Kompleksitas dan running time• Kompleksitas algoritma ini adalah O(n).• Running time brute force adalah : n-1 multiplications

Kekuatan dan kelemahan brute force 

Kekuatan: 

1. Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability). 
2. Metode brute force sederhana dan mudah dimengerti. 
3. Metode brute force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks. 
4. 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

1. Metode brute force jarang menghasilkan algoritma yang mangkus. 
2. Beberapa algoritma brute force lambat sehingga tidak dapat diterima. 
3. Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya. 

Ken Thompson (salah seorang penemu Unix) mengatakan: “When in doubt, use brute force”, faktanya kernel Unix yang asli lebih menyukai algoritma yang sederhana dan kuat (robust) daripada algoritma yang cerdas tapi rapuh.

Best First Search

• Teknik pencarian Best First Search merupakan kombinasi antara Depth First Search danBreadth First Search.

• Teknik ini memperbolehkan pencarian dengan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node yang lebih tinggi memiliki nilai heuristik yang lebih buruk.

• Tak seperti Hill Climbing, teknik Best First Search mempunyai kemampuan melakukan koreksi terhadap suatu langkah yang salah yang telah dipilih lebih dulu.

• Ini merupakan salah satu keuntungan utama Best First Search daripada teknik Hill ClimbingBest First Search bisa dijalankan dengan dua cara, yakni : OR Graph dan Algoritma A*.

->OR Graph
Untuk menjalankan cara ini, dibutuhkan 2 antrian, yakni OPEN dan CLOSED.

– Suatu node disebut open apabila node tersebut telah dibangkitkan dan sudah memiliki fungsi heuristik tetapi belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi.


– Suatu node disebut closed jika node tersebut telah diperluas untuk membangkitkan turunannya.


-> Algoritma A*

– Untuk mengukur kebaikan dari suatu node dalam algoritma A*, diperlukan dua fungsi biaya, yakni biaya heuristik dan biaya pembangkitan. Biaya heuristik mengukur jarak dari node x yang sekarang menuju ke tujuan dan dinyatakan dengan h(x). Sedangkan biaya pembangkitan node x yang dinyatakan dengan g(x) adalah untuk mengukur jarak dari node x ke node awal dalam graph. Total fungsi biaya yang dinyatakan dengan f(x) adalah jumlah g(x) tambah h(x).


– G(x) dapat diukur dengan mudah saat node x dibangkitkan melalui beberapa transisi keadaan. Misalnya, jika node x dibangkitkan dari node awal melalui transisi keadaan m, biaya g(x) akan menjadi proporsional ke m. Lalu, bagaimana mengevaluasi h(x)? Kemungkinan bahwa h(x) adalah biaya yang keluarkan untuk mencapai tujuan. Jelasnya, biaya apapun dapat dinyatakan sebagai h(x) melalui prediksi. Biaya yang diprediksi untuk h(x) dinyatakan dengan h’(x). Oleh karena itu, biaya total yang diprediksikan dinyatakan dengan f’(x) di mana:

F’(x) = g(x) + h’(x)