TUGAS TAMBAHAN MATERI "METODE DIVIDE AND CONQUER"
METODE DIVIDE AND CONQUER
KELOMPOK 2
1. Dinda Yudhia Pertiwi NIM 13160671
2. Sartika Damayanti NIM 13160609
3. Husna Amrulloh NIM 13161170
Pengertian Devide and Conquer
—Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.
Membangun Algoritma Divide dan Conquer
—Sebuah algoritma divide and conquer atau selanjutnya disebut dengan D&C memiliki 3 langkah yaitu:
1. Divide(Memecah)pada langkah ini kita memecahkan masalah atau data dalam bentuk yang sama,tetapi dalam ukuran yang lebih kecil.pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif,sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
2. Conquer(Menaklukan):dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama,dengan menggunakan algoritma sederhana
3. Combine(Menggabungkan):seteleh menjalankan langkah conquer,tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada,untuk mendapatkan hasil akhir kalkulasi.Langkah combine mencoba mencapai hal tersebut .
Bentuk Umum Proses Metode D And C
[ n input]
||
[n input 1] [n input 2] [n input 3] [n input k]
|| || || ||
[suproblem 1] [suprob 2] [suprob 3] [suprob k]
|| || || ||
[subsolusi 1] [subsolusi 2] [subsolusi 3] [subsolusi k]
||
[solusi optimal]
— Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya.
—Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.
— Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri).
— Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.
—
Penerapan Algoritma
— Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer.
— Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandang
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:
sebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:
— Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).
— Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).
— Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.
— Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).
— Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.
SORTING
1. Metode Selection Sort
2. Metode Buble Sort
3. Metode Merge Sort
4. Metode Quick Sort
5. Metode Insertion.
Hal yg mempengaruhi Kecepatan Algoritma Sort :
Jumlah Operasi Perbandingan & Jumlah Operasi
Pemindahan Data .
SELECTION SORT
Tehnik pengurutan dengan cara pemilihan
elemen atau proses kerja dengan memilih
elemen data terkecil untuk kemudian
dibandingkan & ditukarkan dengan elemen pd
data awal, dst s/d seluruh elemen sehingga akan
menghasilkan pola data yang telah disort.
Prinsip Kerja dari Teknik Selection Sort
1. Pengecekan dimulai data ke-1 sampai dengan data ke-n .
2. Tentukan bilangan dengan Index terkecil dari data bilangan tersebut .
3. Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 )dari data bilangan tersebut .
4. Lakukan langkah 2 dan 3 untuk bilanganberikutnya ( I= I+1 ) sampai didapatkanurutan yg optimal.
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 22 10 15 3 8
2
Langkah 3 : 2 10 15 3 8 22
Langkah 4 : Ulangi langkah 2 dan 3 .
Iterasi 2
Langkah 1: 2 10 15 3 8 22
Langkah 2: 2 10 15 3 8 22
Langkah 3: 2 3 15 10 8 22
Langkah 4: Ulangi langkah 2 dan 3 .
Lakukan Iterasi selanjutnya sampai iterasi
ke-6 .
QuickSort
Metode QuickSort sering disebut metode partition
exchange sort, Diperkenalkan oleh C.A.R. Hoare. Pada
metode ini jarak kedua elemen yang akan ditukarkan
nilainya ditentukan cukup besar.
Misal ada N elemen dalam keadaan urut turun, adalah
mungkin untuk mengurutkan N elemen tersebut dengan
N/2 kali, yakni pertama kali menukarkan elemen paling kiri
dengan paling kanan, kemudian secara bertahap menuju
ke elemen yang ada di tengah. Tetapi hal ini hanya bisa
dilakukan jika kita tahu pasti bahwa urutannya adalah urut turun.
Secara garis besar metode ini dijelaskan sebagai berikut,
misal kita akan mengurutkan vektor A yang mempunyai N
elemen. Kita pilih sembarang dari vektor tersebut, biasanya
elemen pertama misalnya X. kemudian semua elemen
tersebut disusun dengan menempatkan X pada posisi J
sedemikian rupa sehingga elemen ke 1 sampai ke j-1
mempunyai nilai lebih kecil dari X dan elemen ke J+1
sampai ke N mempunyai nilai lebih besar dari X. Dengan
demikian kita mempunyai dua buah subvektor, subvektor
pertama nilai elemennya lebih keci dari X, subvektor kedua
nilai elemennya lebih besar dari X.
Pada langkah berikutnya, proses diatas diulang pada
kedua subvektor, sehingga kita akan mempunyai empat
subvektor. Proses diatas diulang pada setiap subvektor
sehingga seluruh vektor semua elemennya menjadi
terurutkan.
Contoh:
Subvektor Kiri : 23 45 12 24 56 {12 ,23 ,16 ,23, 12 ,16 ,23, 23,}
Subvektor Kanan : 56 34 27 23 16 {45, 24, 56, 34, 27, 24, 34 ,27 ,45, 56, 24 ,27 ,34
,45, 56 } .
QUICK SORT
— Termasuk pada pendekatan sulit membagi ,mudah menggabungkan (hard split/easy join)
— Tabel A dibagi ( istilahnya : dipartisi) menjadi A1 dan A2 sedemikian sehingga elemen-elemen A1 ≤ elemen-elemen A2
— Cara pemilihan pivot :
1. Pivot = elemen pertama /elemen terakhir/elemen tengah tabel.
2. Pivot dipilih secara acak dari salah satu elemen tabel.
3. Pivot = elemen median tabel.
INSERTION SORT
Prinsip dasar Insertion adalah secara berulang-ulang
menyisipkan / memasukan setiap elemen. ke dlm
posisinya / tempatnya yg benar.
1. Prinsip Kerja Insertion Sort adalah
2. Pengecekan mulai dari data ke-1 sampai data ke-n
3. Bandingkan data ke-I ( I = data ke-2 s/d data ke-n )
4. Bandingkan data ke-I tersebut dengan datasebelumnya (I-1), Jika lebih kecil maka data tersebut dapat disisipkan ke data awal sesuai dengan posisisi yang seharusnya
5. Lakukan langkah 2 dan 3 untuk bilanganberikutnya ( I= I+1 ) sampai didapatkan urutan yang optimal.
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1: 22 10 15 3 8 2
Langkah 2: 22 10 15 3 8 2
Langkah 3: 10 22 15 3 8 2
Langkah 4: Ulangi langkah 2 dan 3
Iterasi 2
Langkah 1: 10 22 15 3 8 2
Langkah 2: 10 22 15 3 8 2
Langkah 3: 10 15 22 3 8 2
Langkah 4: Ulangi langkah 2 dan 3
Lakukan Iterasi selanjutnya sampai iterasi
ke- 6
Catatan : Setiap ada pemindahan, maka elemen.
Yang sudah ada akan di insert sehingga akan bergeser kebelakang.
MERGE SORT
Prinsip Kerja Merge Sort adalah :
• Kelompokan deret bilangan kedalam 2 bagian, 4 bagian, 8 bagian, ......dst à (2)
• Urutkan secara langsung bilangan dalam n kelompok tsb.
• Lakukan langkah diatas untuk kondisi bilangan
yg lain sampai didapatkan urutan yg optimal .
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
Langkah 2 : 10 22 3 15 2 8
Iterasi 2
Langkah 1 : 10 22 3 15 2 8
Langkah 2 : 3 10 15 22 2 8
Iterasi 3
Langkah 1 :3 10 15 22 2 8
Langkah 2 :2 3 8 10 15 22
— Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes
— Sekarang strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer
— Objek Persoalan yang dibagi:masukan(input) atau instances persoalan yang berukuran seperti:-tabel(larik),-matriks,-eksponen,-dll,bergantung persoalannya.
— Tiap-tiap upa-masalah mempunyai karakteristik yang sama(the same type)dengan karakteristik masalah asal
— Sehingga metode
— Divide and Conquer lebih natural diungkapkan dengan skema rekursi
Kompleksitas Algoritma Quick Sort
1. Kasus terbaik terjadi bila pivot adalah elemen median sedemikian sehingga kedua tabel berukuran relatif sama setiap kali pempartisian.
Penyelesaian (seperti pada Merge Sort) :
T(n)=2T(n/2) + cn = na +cn ²log n = O(n ²log n).
2. Kasus terburuk (worst case)
— Kasus ini terjadi bila pada setiap partisi pivot selalu elemen maksimum (atau elemen minimum)tabel.
— Kasus jika tabel sudah terurut menarik/menurun
Kompleksitas waktu pengurutan:
penyelesaian (seperti padan insertion sort)
T(n) = T(n-1) + cn = O(n²).
3. Kasus rata - rata (average case)
Kasus ini terjadi jika pivot dipilih secara acak dari elemen tabel ,dan peluang setiap elemen dipilih menjadi pivot adalah sama.
Tavrg(n) = o(n²log n)
—Kompleksitas waktu algoritma : penyelasaian (seperti pada insertion sort)
T(n) = O(n²).
Persoalan Minimum dan Maksimum (MinMaks)
— Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :
— Ide dasar algoritma secara Divide and Conquer :
