1. ALGORITMA MARGE SORT
1.1 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.
1.2. 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).
2. ALGORITMA BRUTE FORCE
2.1. 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.
2.2. 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.
3. ALGORITMA BUBBLE SORT
3.1. 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.
3.2.
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.
3.2. 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.
3.2.1 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).
3.2.2
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.
4. 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.
I. ALGORITMA SEARCHING
1. Pencarian Secara Linear (Sequential Search)
Sequential
Search adalah proses membandingkan setiap elemen
larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen
yang dicari ditemukan atau seluruh elemen sudah diperiksa. Algoritma
pencarian secara linear digunakan untuk mencari sebuah nilai pada tabel
sembarang. Ada dua macam cara pencarian pada tabel. Algoritma ini mempunyai dua
jenis metode yaitu dengan boolean dan tanpa boolean. Algoritma pencairan secara
linear melakukan pengulangan sebanyak 1 kali untuk kasus terbaik (value sama
dengan elemen pertama dalam tabel) dan Nmax kali untuk kasus terburuk. Sehingga
algoritma ini mempunyai kompleksitas algoritma O(n).
2. Binary
Search
2.1 Algoritma Binary
Search
Binary Search adalah algoritma
pencarian yang lebih efisien daripada algorima Sequential Search. Hal
ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel.
Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya
sudah terurut baik menaik maupun menurun. Pada intinya, algoritma ini
menggunakan prinsip divide and conquer, dimana sebuah masalah atau
tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih
kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian
dari tabel itu saja. Algoritma ini bekerja dengan cara memilih record dengan
indeks tengah dari tabel dan membandingkannya dengan record yang hendak
dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel
tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali
secara rekursif.
1.2
Kompleksitas Waktu
Kompleksitas waktu terbaik algoritma ini adalah 1, sedangkan
kompleksitas waktu terburuknya 2log n. Kompleksitas waktu terburuk ini
dicapai pada kasus dimana record tidak ditemukan dalam tabel. Pada kasus
ini, algoritma melakukan pembagian tabel hingga ukuran tabel sebesar 1 elemen.
Jumlah langkah tersebut adalah 2log n. Karena pada setiap langkah dilakukan
perbandingan yang merupakan basis dari penghitungan kompleksitas waktu algoritma
pencarian, maka kompleksitas waktu terburuk algoritma ini adalah 2log n.
1.3 Keunggulan
Binary Search
Keunggulan utama dari algoritma binary search adalah
kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential
search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary
search dalam mencari sebuah record dalam sebuah tabel lebih kecil
daripada waktu yang dibutuhkan algoritma sequential search.
3. PERBANDINGAN
Pada algoritma
binary search adalah kompleksitas algoritmanya yang lebih kecil daripada
kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang
dibutuhkan algoritma binary search dalam mencari sebuah record dalam
sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential
search. Sedangkan sequential search adalah proses membandingkan setiap
elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai
elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Sehingga
cocok untuk pencarian pada data yang tidak terurut.
Komentar
Posting Komentar