Metode Divide 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. Langkah-langkah umum algoritma Divide and Conquer :
- Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
- Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
- Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap 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.
SORTING
- Metode Selection Sort
- Metode Buble Sort
- Metode Merge Sort
- Metode Quick Sort
- 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 pada data awal, dst s/d seluruh elemen sehing akan menghasilkan pola data yg telah disort.
Prinsip Kerja dari Teknik Selection Sort ini adalah :
- Pengecekan dimulai data ke-1 sampai dengan data ke-n
- Tentukan bilangan dengan Index terkecil dari data bilangan tersebut
- Tukar bilangan dengan Index terkecil tersebut dengan bilangan pertama ( I = 1 ) dari data bilangan tersebut.
- Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) 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 : 2 22 10 15 3 8
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
BUBBLE SORT
Tehnik Sort yg bekerja dgn menggunakan prinsip gelembung (bubble) udara yg akan bergerak naik ke atas secara satuper satu.
Prinsip Kerja dari Bubble Sort adalah :
- Pengecekan mulai dari data ke-1 sampai data ke-n
- Bandingkan data ke-n dengan data sebelumnya (n-1)
- Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yg ada didepannya ( sebelumnya ) satu persatu (n-1,n-2,n-3,....dst).
- Jika lebih besar maka tidak terjadi pemindahan
- Ulangi langkah 2 dan 3 s/d sort optimal.
Contoh : 22 10 15 3 8 2
terasi 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: 22 10 15 3 2 8
Langkah 4: Ulangi langkah 2 dan 3
Hasil iterasi 1 : 2 22 10 15 3 8
QUICK SORT
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.
INSERTION SORT
Prinsip dasar Insertion adalah secara berulang-ulang menyisipkan / memasukan setiap elemen. ke dlm posisinya / tempatnya yg benar.
- Prinsip Kerja Insertion Sort adalah
- Pengecekan mulai dari data ke-1 sampai data ke-n
- Bandingkan data ke-I ( I = data ke-2 s/d data ke-n )
- Bandingkan data ke-I tersebut dengan data sebelumnya (I-1), Jika lebih kecil maka data tersebut dapat disisipkan ke data awal sesuai dgn posisisi yg seharusnya
- Lakukan langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) 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 : 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 (2n)
- Urutkan secara langsung bilangan dalam 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
Sekian pembahasan dari Metode Divide And Conquer. Semoga bermamfaat dan terima kasih.