Sejarah, Definisi dan Cara Kerja Divide and Conquer

 A. Sejarah Divide and Conquer

 Pada   zaman   dahulu,   divide   and   conquer merupakan strategi militer  yang  dikenal dengannama divide  ut  imperes.  Saat  ini  strategi  tersebut  menjadi strategi fundamental di dalam ilmu komputer dengan nama   divide   and   conquer.   Algoritma   divide   and conquer  ini  ditemukan  oleh  seorang  ilmuwan  Rusia bernama  Anatolii  Alexeevich  Karatsuba  pada  tahun 1960.  Pada  mulanya  beliau  menemukan  algoritma yang  lebih  mangkus   untuk   mengalikan   dua  buah bilangan bulat yang besar.

Algoritma divide and conquer di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang disortir untuk memfasilitasi pencarian berasal dari setidaknya sejauh Babylonia pada 200 SM. Algoritma divide and conquer kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Contoh awal dari algoritma bagi dan aklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian.

Algoritma D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan tepat adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945. Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 yang dapat mengalikan dua angka n- digit dalam  O operasi (dalam notasi Big O). Algoritma ini membantah dugaan tahun 1956 Andrey Kolmogorov  operasi akan diperlukan untuk tugas itu. Sebagai contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait dengan jenis radix, dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.

B. 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

 

 

 Referensi

https://ndawindaayu.blogspot.com/2020/12/divide-and-conquer.html

https://yogafirza.blogspot.com/2019/02/algoritma-divide-dan-conquer.html