Metode Devide and Conquer
Prinsip dasar metode Devide and Conquer atau D and C adalah membagi n input menjadi k subset input yang berbeda (1 < k ≤ n). Dari k subset input yang berbeda tersebut akan terdapat k subproblem, dimana setiap subproblem mempunyai solusi masing-masing sehingga diperoleh k subsolusi. Dari k subsolusi tersebut akan diperoleh solusi yang optimal atau solusi yang diharapkan. Bentuk Umum Proses Metode D And C dpt dilihat sbb :
Jika subproblem dianggap masih relatif besar, maka metode D and C dapat digunakan lagi.
Dengan kata lain bahwa metode D and C ini dilakukan dengan membagi setiap input atau permasalahan sampai dengan suatu input atau permasalahan tidak dapat dibagi lagi.
Setelah itu, dari pembagian tadi akan ditemukan solusi yang optimal.
SORTING
Sorting adalah suatu usaha untuk melakukan pengurutan (sorting) sekelompok data dalam suatu array, dilakukan terhadap suatu himpunan yang berisikan elemen bilangan ataupun himpunan karakter (string).
Dalam melakukan proses sorting terdapat beberapa hal yang dapat mempengaruhi kecepatan proses sorting antara lain :
Jumlah operasi perbandingan yang dilakukan, dan
Jumlah operasi pemindahan data yang dilakukan.
Makin banyak jumlah operasi perbandingan maka makin lama proses sorting tersebut berjalan.
Begitu pula dengan operasi pemindahan data, makin banyak jumlah operasi pemindahan data maka makin lama proses sorting tersebut dilakukan.
Metode-Metode dalam Sorting
Metode Selection Sort,
Metode Buble Sort,
Metode Merge Sort,
Metode Quick Sort,dan
Metode Insertion Sort.
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, dan seterusnya sampai dengan seluruh elemen sehingga akan menghasilkan pola data yg telah di sorting.
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 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 .
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
BUBLE SORT Tehnik Sort yang bekerja dengan menggunakan prinsip gelembung (buble) udara yang akan bergerak naik ke atas secara satuper satu.
Prinsip Kerja dari Buble 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 : 2 22 10 15 3 8
Langkah 4 : Ulangi langkah 2 dan 3
Iterasi 2
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 sebelunya yaitu 3.
Langkah 3 : 2 3 22 10 15 8
Langkah 4 : Ulangi langkah 2 dan 3
Lakukan Iterasi selanjutnya sampai iterasi ke- 6
QUICK SORT Sort dengan iterasi secara urut dari posisi elemen 1, ke-2 dan seterusnya. Tukarkan setiap elemen pada posisi tersebut dengan elemen lain yang nilainya memang seharusnya berada pada posisi tersebut.
Prinsip Kerja dari Quick Sort adalah :
Tentukan Lower Bound (Batas Bawah) & Upper Bound (Batas Atas)
Bandingkan Lower Bound (LB) dengan Upper Bound (UB)
Jika LB>UB, Tukar (cari operasi perbandingan yang optimal/terkecil)
Jika LB =< UB, maka Next Upper Bound & Lower Bound
Ulangi langkah diatas s/d sort.
Contoh : 22 10 15 3 8 2
Iterasi 1
1 2 3 4 5 6
Langkah 1 : 22 10 15 3 8 2
LB UB
Langkah 2 :2 10 15 3 8 22
Iterasi 2
Langkah 1 : 2 10 15 3 8 22
LB/UB
Langkah 2 :2 10 15 3 8 22
LB UB
Iterasi 3
Langkah 1 :2 10 15 3 8 22
LB UB
Langkah 2 :2 8 15 3 10 22
Iterasi 4
Langkah 1 :2 8 15 3 10 22
LB UB
Langkah 2 :2 3 15 8 10 22
Lakukan Iterasi selanjutnya sampai iterasi
ke- 6
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
Iterasi 3
Langkah 1 :3 10 15 22 2 8
Langkah 2 :2 3 8 10 15 22
