PERTEMUAN 10

METODE DIVIDE AND
CONQUER

Ø Pengertian
·        Divide and Conquer adalah strategi militer yang di kenal dengan nama divide ut imperes,sekarang menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer.
Membagi atau memecahkan (menyelesaikan) persoalan menjadi beberapa upa-masalah secara rekursif  yang memiliki kemiripan dengan persoalan semula namun berukuran lebih kecil (idealnya berukuran hampir sama)

·        Bentuk umum prosesor Metode D and C dapat dilihat sbb

contohnya sebagai berikut :



Ø SORTING
1)   Metode selection Sort
2)   Metode Buble Sort
3)   Metode Merge Sort
4)   Metode Quick Sort
5)   Metode Insertion
Ø Hal yang mempengaruhi kecepatan Algoritma Sort seperti :
1)   Jumlah Operasi Perbandingan
2)   Jumlah Operasi Permindahan Data

Ø SELECTION SORT
Yaitu Teknik pengurutan dengan cara pemilihan elemen atau proses kerja dengan memilih elemen data terkecil untuk kemudian di bandingkan & ditukarkan dengan elemen pada data awal. Dan seterusnya sampai seluruh elemen sehingga akan akan menghasilkan pola data yang telah disort. Yaitu contohnya sebagai berikut :
ü Persoalan : misalkan diberikan tabel A yang berukuran N elemen dan sudah berisi nilai integer. Carilah nilai minimum dan nila maksimum sekaligus di dalam tabel tersebut.

Ø 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 bilangan berikutnya ( i=i+1 ) sampai di dapatkan 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:       2         10       15       3         8         22
Langkah 4:       Ulangi langkah 2 dan 3

  •     BUBBLE SORT

Teknik sort yang bekerja dengan menggunakan prinsip gelembung(bubble) udara yang akan bergerak naik ke atas secara satuper satu.

       I            Prinsip kerja dari bubble sort adalah :
  1. 1)   Pengecekan mulai dari data ke-1 sampai data ke-n
  2. 2)   Bandingkan data ke-n dengan data sebelumnya (n-1)
  3. 3)   Jika lebih kecil maka pindahkan bilangan tersebut dengan bilangan yang ada di depannya (sebelumnya) datu persatu (n-1,n-2,n-3...dst)
  4. 4)   Jika lebih besar maka tidak terjadi pemindahan
  5. 5)   Ulangi langkah 2 dan 3 s/d sort optimal.

                   Contohnya:
                   Langkah 1:       2         22       10       15       3         8
                   Langkah 2:       2         22       10       15       3         8
-         8>3 maka 8 tidak pindah, untuk selanjutnya bandingkan data sebelumnya yaitu 3.
                   Langkah 3:       2         22       10       3         15       8
                   Langkah 4:       Ulangi langkah 2 dan 3
                   Hasil iterasi 2: 2         3         22       10       15       8
                   Akukan iterasi selanjutnya sampai iterasi ke-6

  •        QUICKSORT



Metode QuickSort sering disebut metode prtition exchange sort, di perkenalkan oleh C.A.R Hoare. Pada metode ini jarak kedua elemen yang akan ditukarkan nilainya di tentukan 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 in hanya bisa di lakukkan 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 sdemikian rupa sehingga elemen ke 1 sampai ke j-1 mempunyai nilai lebih kecil dari X dn 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 kecil dari X, subvektor kedua nilai elemenna lebih besar dari X.
Pada langkah berikutnya, proses di atas di ulang pada kedua subvektor, sehingga kita akan mempunyai empat subvektor, sehingga kita akan mempunyai empat subvektor. Proses di atas di ulang pada setiap sybvektor sehingga seluruh vektor semua elemennya menjadi terurutkan.

Contoh sebagai berikut :
 

  •      INSERTIION SORT

Prinsip dasar insertion adalah secara berulang-ulang menyisipkan atau memasukan setiap elemen. Ke dalam posisinya ataau tempatnya yang benar.
  1. 1)   Prinsip kerja insertion sort adalah
  2. 2)   Pengecekan mulai dari data ke-1 sampai data ke-n
  3. 3)   Bandingkan data ke-I(I=data ke-2 s/d data ke-n)
  4. 4)   Bandingkan data ke-I tersebut dengan data sebelumnya (I-1), jika lebih kecil maka data tersebut dapat disisipkan ke data awal sesuai dengan posisi yang seharusnya.
  5. 5)   Lakukkn langkah 2 dan 3 untuk bilangan berikutnya ( I= I+1 ) sampai di dapatkan urutan yang optimal.


Contohnya sebagai berikut :
 

  •     MARGE SORT

Prinsip kerja Merge Sort adalah :
  1. a)    Kelompokan deret bilangan keddalam 2 bagian, 4 bagian, 8 bagian, .....dst
  2. b)    Urutkan secara langsung bilangan dalam kelompok tsb.
  3. c)     Lakukan langkah di atas untuk kondisi bilngan yang lain sampai di dapatkan urutan yang optimal

                   Contohnya sebagai berikut :


Paralel, P. (n.d.). Algoritma Divide and Conquer, 1–10.
(Paralel, n.d.)
                             


Komentar

Posting Komentar