ALGORITMA MARGE SORT
Konsep Algoritma Merge
Sort
Secara konseptual, untuk sebuah array berukuran n, Merge Sort bekerja sebagai berikut:
- Jika bernilai 0 atau 1, maka array sudah terurut. Sebaliknya:
- Bagi array yang tidak terurut menjadi dua subarray, masing-masing berukuran n/2.
- Urutkan setiap sub-array. Jika sub-array tidak cukup kecil, lakukan rekursif langkah 2 terhadap sub-array.
- Menggabungkan dua sub-array kembali menjadi satu array yang terurut.
Merge sort menggabungkan dua ide utama untuk meningkatkan runtimenya:
- Array kecil akan mengambil langkah-langkah untuk menyortir lebih sedikit dari array besar.
- 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:
- 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.
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• 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• =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:
- 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
- Metode brute force jarang menghasilkan algoritma yang mangkus.
- Beberapa algoritma brute force lambat sehingga tidak dapat diterima.
- 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.
ALGORITMA BUBBLE SORT
Langkah pengurutan dalam Bubble Sort
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. Misalkan kita mempunyai sebuah array dengan elemen-elemen “4 2
5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort
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 dalamalgoritma bubblesort
adalah tidak ada satupun penukaranpada suatu pass, sehingga pass ketiga
dibutuhkan untukmemverifikasi keurutan array tersebut.
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 elemen-elemen 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.
Kelebihan dan Kekurangan Algoritma Bubble Sort
Setiap algoritma memiliki kelebihan dan kekurangannya masing-masing,
demikian pula dengan algoritma Bubble Sort. Kelebihan dan kekurangan
dari algoritma Bubble Sort dapat dilihat dari karakteristik algoritma
Bubble Sort itu sendiri. Berikut ini adalah beberapa kelebihan dan
kekurangan dari algoritma Bubble Sort.
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 sintax dalam pembuatan 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.
PERBANDINGAN
Algoritma BubbleSort
adalah algoritma yang simpel dan mudah dipelajari, selain itu memiliki
definisi terurut yang jelas dalam algoritmanya. Algoritma ini juga
memiliki ciri khas, yaitu “kura-kura dan kelinci”. Akan tetapi,
algoritma BubbleSort memiliki kelemahan, yaitu kompleksitas algoritma
O(n2) pada average case dan worst case, sehingga menjadikan algoritma
ini tidak efektif dalam pengurutan. Oleh karena itu, banyak diciptakan
variasi BubbleSort, mulai dari modifikasi algoritma hingga penambahan
langkah baru dalam bentuk comb sort dan cocktail sort.
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). Sedangkan algoritma
bruto force merupakan algoritma yang lambat dan kurang kreatif seperti
algoritma lainnya.
Tidak ada komentar:
Posting Komentar