Pengertian Algoritma Devide & Conquer
Algoritma 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 Devide & Conquer
>Divide: membagi persoalan menjadi beberapa sub sub masalah yang memiliki
kemiripan dengan persoalan semula namun berukuran lebih kecil(idealnya
berukuran hampir sama).
>Conquer (solve): dalam langkah ini kita mencoba menyelesaikan masalah atau
data yang telah dipecahkan pada langkah pertama, dengan menggunakan
algoritma sederhana.
>Combine: menggabungkan solusi masing-masing sub sub masalah sehingga
membentuk solusi atau hasil akhir dari persoalan semula.
Skema Umum Divide & Conquer
Pengertian Insertion Sort
Insertion Sort adalah sebuah metode pengurutan data
dengan menempatkan setiap elemen data pada
posisinya dengan cara melakukan perbandingan
data-data yang ada.
Contoh Data
Data : 6 8 2 1 4
Penjelasan :
Pada iterasi 2, Gabungkan SubData 6 dengan 8 sembari di sorting. Karena 8 > 6 maka, tidak terjadi pertukaran. Perbandingan
dilakukan dari SubData paling belakang sampai SubData Pertama.
Pada iterasi 4, Gabungkan SubData 6, 8 dan 2 sembari di sorting. Perbandingan dilakukan dari Data yang paling belakang. 2
bandingkan dengan 8. Karena, 2 < 8 maka, SubData 2 bertukar tempat dengan SubData 8. Kemudian, bandingkan lagi 2 dengan 6.
Karena 2 < 6 maka, SubData 2 bertukar tempat dengan SubData 6.
Pada Iterasi 4, Gabungkan SubData 2, 6, 8 dan 1 sembari di sorting. Bandingkan SubData 1 dengan SubData 8. Karena 1 < 8 maka,
SubData 1 bertukar tempat dengan SubData 8. Lanjut lagi bandingkan SubData 1 dengan SubData 6. Karena, 1 < 6 maka SubData 1
bertukar tempat dengan SubData 6. Bandingkan lagi SubData 1 dengan SubData 2. Karena 1 < 2 maka, SubData 1 bertukar tempat
dengan SubData 2.
Pada iterasi 6, Gabungkan SubData 1, 2, 6, 8 dan 4 sembari di sorting. Bandingkan SubData 4 dengan SubData 8. Karena 4 < 8 maka,
SubData 4 bertukar tempat dengan SubData 8. Bandingkan lagi SubData 4 dengan SubData 6. Karena 4 < 6 maka, SubData 4 bertukar
tempat dengan SubData 6. Bandingkan lagi SubData 4 dengan SubData 2. Karena 4 > 2 maka, tidak terjadi pertukaran. Dan hentikan
proses perbandingan.
Data setelah di Sorting : 1 2 4 6 8
Menggunakan Algoritma Divide and Conquer
Data : 6 8 2 1 4
Lakukan pembagian data tersebut secara satu per satu dimulai dari data pertama sampai data terakhir.
DIVIDE, CONQUER dan SOLVE :
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
INSERT SORT :
6 8 2 1 4 Karena 1 < 2 , 2 < 4 Maka :
6 8 1 2 4 Karena 1 < 8 , 2 < 8, 4 < 8 Maka :
6 1 2 4 8 Karena 1 < 6, 2 < 6, 4 < 6, 6 < 8 Maka :
1 2 4 6 8
Algoritma 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 Devide & Conquer
>Divide: membagi persoalan menjadi beberapa sub sub masalah yang memiliki
kemiripan dengan persoalan semula namun berukuran lebih kecil(idealnya
berukuran hampir sama).
>Conquer (solve): dalam langkah ini kita mencoba menyelesaikan masalah atau
data yang telah dipecahkan pada langkah pertama, dengan menggunakan
algoritma sederhana.
>Combine: menggabungkan solusi masing-masing sub sub masalah sehingga
membentuk solusi atau hasil akhir dari persoalan semula.
Skema Umum Divide & Conquer
Pengertian Insertion Sort
Insertion Sort adalah sebuah metode pengurutan data
dengan menempatkan setiap elemen data pada
posisinya dengan cara melakukan perbandingan
data-data yang ada.
Contoh Data
Data : 6 8 2 1 4
Penjelasan :
Pada iterasi 2, Gabungkan SubData 6 dengan 8 sembari di sorting. Karena 8 > 6 maka, tidak terjadi pertukaran. Perbandingan
dilakukan dari SubData paling belakang sampai SubData Pertama.
Pada iterasi 4, Gabungkan SubData 6, 8 dan 2 sembari di sorting. Perbandingan dilakukan dari Data yang paling belakang. 2
bandingkan dengan 8. Karena, 2 < 8 maka, SubData 2 bertukar tempat dengan SubData 8. Kemudian, bandingkan lagi 2 dengan 6.
Karena 2 < 6 maka, SubData 2 bertukar tempat dengan SubData 6.
Pada Iterasi 4, Gabungkan SubData 2, 6, 8 dan 1 sembari di sorting. Bandingkan SubData 1 dengan SubData 8. Karena 1 < 8 maka,
SubData 1 bertukar tempat dengan SubData 8. Lanjut lagi bandingkan SubData 1 dengan SubData 6. Karena, 1 < 6 maka SubData 1
bertukar tempat dengan SubData 6. Bandingkan lagi SubData 1 dengan SubData 2. Karena 1 < 2 maka, SubData 1 bertukar tempat
dengan SubData 2.
Pada iterasi 6, Gabungkan SubData 1, 2, 6, 8 dan 4 sembari di sorting. Bandingkan SubData 4 dengan SubData 8. Karena 4 < 8 maka,
SubData 4 bertukar tempat dengan SubData 8. Bandingkan lagi SubData 4 dengan SubData 6. Karena 4 < 6 maka, SubData 4 bertukar
tempat dengan SubData 6. Bandingkan lagi SubData 4 dengan SubData 2. Karena 4 > 2 maka, tidak terjadi pertukaran. Dan hentikan
proses perbandingan.
Data setelah di Sorting : 1 2 4 6 8
Menggunakan Algoritma Divide and Conquer
Data : 6 8 2 1 4
Lakukan pembagian data tersebut secara satu per satu dimulai dari data pertama sampai data terakhir.
DIVIDE, CONQUER dan SOLVE :
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
6 8 2 1 4
INSERT SORT :
6 8 2 1 4 Karena 1 < 2 , 2 < 4 Maka :
6 8 1 2 4 Karena 1 < 8 , 2 < 8, 4 < 8 Maka :
6 1 2 4 8 Karena 1 < 6, 2 < 6, 4 < 6, 6 < 8 Maka :
1 2 4 6 8
Tags:
Semester 4