Algoritma Divide and Conquer: Arti, Kelebihan, Contoh, dan Implementasinya

Ilmu komputer menjadi suatu bidang ilmu yang seolah-olah tidak ada habisnya. Dari waktu ke waktu terus berkembang. Berbagai hal yang dulu terasa mustahil, saat ini sudah banyak yang dapat diwujudkan. 

Cukup banyak hal yang perlu dipahami dan dikuasai untuk menggali dan mempelajari ilmu komputer. Di antaranya adalah algoritma. Salah satu algoritma yang menjadi fundamental dalam ilmu komputer adalah Algoritma Divide and Conquer.

Di bawah ini kami berikan penjelasan lengkap tentang Algoritma Divide and Conquer:

Pengertian Algoritma Divide and Conquer

Algoritma Divide and Conquer adalah algoritma yang digunakan dalam ilmu atau pemrograman komputer. Algoritma ini memiliki prinsip memecah-mecah suatu permasalahan yang terlalu besar hingga menjadi bagian-bagian yang lebih kecil, supaya menjadi lebih mudah dalam penyelesaiannya. Dengan kata lain, permasalahan tersebut akan diselesaikan secara terpisah. 

Konsepnya, setelah suatu permasalahan dibagi menjadi beberapa bagian kecil, maka akan diselesaikan perbagian atau per sub masalahnya. Kemudian solusi sub masalah tersebut akan digabungkan menjadi solusi akhir atau solusi keseluruhan masalah yang lebih besar tersebut. 

Gambaran cara kerja dari algoritma Divide and Conquer seperti berikut ini:

1. Divide

Cara kerja algoritma divide yaitu:

• Pertama-tama suatu permasalahan akan dibagi menjadi dua atau beberapa sub masalah yang lebih kecil yang serupa dengan permasalahan yang aslinya
• Pembagian masalah menjadi submasalah akan dilakukan hingga masalah tersebut sudah tidak dapat dibagi lagi
• Setelah masalah dibagi dan menjadi submasalah yang terkecil, maka akan dapat dipecahkan dengan lebih mudah

2. Conquer

Sedangkan cara kerja algoritma Conquer sebagai berikut:

• Permasalahan akan dibagi menjadi sub-sub masalah yang lebih kecil
• Kemudian setiap submasalah akan dipecahkan dengan cara terpisah atau masing-masing
• Pemecahan sub-sub masalah tersebut akan dilakukan dengan menggunakan algoritma yang sama maupun dengan algoritma yang berbeda, tergantung pada masalah yang dihadapi

3. Combine

Yang terakhir yaitu cara kerja combine atau menggabungkan hasil dari solusi yang ada. Cara melakukannya yaitu:

• Memecahkan masalah menjadi beberapa sub masalah
• Kemudian dicari solusi dari semua submasalah tersebut
• Lalu solusi akhir akan didapatkan dengan cara melakukan penggabungan dari solusi setiap submasalah

Kelebihan Algoritma Divide and Conquer

Penggunaan algoritma Divide and Conquer untuk memecahkan suatu permasalahan pada ilmu atau pemrograman komputer memiliki beberapa kelebihan, di antaranya:

1. Kelebihan dalam skalabilitas. Yaitu dapat digunakan untuk menyelesaikan masalah yang memiliki ukuran berbeda, mulai dari masalah kecil sampai pada masalah yang sangat besar.
2. Kelebihan dalam modularitas. Yaitu memiliki struktur modular yang memungkinkan suatu masalah akan dapat dibagi menjadi beberapa submasalah yang lebih kecil dan terpisah. Dengan demikian akan mudah untuk diimplementasikan dan dipelajari, dan juga dapat digunakan kembali apabila ke depannya ada masalah yang serupa.
3. Kelebihan dalam efisiensi. Algoritma ini dapat menghasilkan solusi yang lebih efisien jika dibandingkan dengan algoritma lainnya. Contohnya, algoritma Merge Sort yang menggunakan teknik Divide and Conquer dalam mengurutkan suatu daftar dalam waktu yang relatif cepat.
4. Kelebihan dalam akurasi. Karena metode ini dapat menghasilkan solusi yang lebih akurat dibandingkan jika menggunakan metode jenis lainnya. Seperti, algoritma quadtree menggunakan teknik Divide and Conquer yang digunakan untuk membangun representasi spasial objek yang terdapat dalam sebuah gambar atau diagram dengan presisi yang tinggi.

Kekurangan Algoritma Divide and Conquer

Sedangkan untuk kekurangan penggunaan algoritma Divide and Conquer adalah sebagai berikut:

1. Overhead. Karena banyak pemanggilan fungsi rekursif yang diperlukan, sehingga menghasilkan overhead yang cukup tinggi serta waktu eksekusinya menjadi lebih lama.
2. Penggunaan memori besar. Terutama apabila sub masalahnya berukuran besar. Tentunya hal ini akan berpengaruh pada kinerja sistem dan juga dapat membatasi skala pemecahan masalah.
3. Kesulitan Pemrograman. Sebab, apabila konsepnya tidak dipahami dengan baik, maka penerapan algoritma ini bisa menjadi sulit diprogram. Sehingga bisa mempersulit proses pengembangan dan pengujian program tersebut.
4. Kesulitan Analisis. Analisis terhadap kinerja algoritma ini bisa lebih sulit jika dibandingkan dengan metode yang lain, karena melibatkan cukup banyak pemanggilan rekursif dan pembagian masalahnya menjadi submasalah yang lebih kecil. Maka dapat menyebabkan kesulitan dalam proses optimasi serta peningkatan kinerja.

Contoh Algoritma Divide and Conquer

Contoh dari algoritma Divide and Conquer adalah:

1. Seperti namanya, merge sort adalah algoritma yang didesain untuk mengurutkan sekelompok bilangan. Ide utamanya yaitu menjadi keseluruhan list atau daftar menjadi komponen yang lebih kecil. Lalu mengurutkan komponen-komponen tersebut untuk kemudian menggabungkannya menjadi sebuah list yang besar.
2. Memecahkan permasalahan Convex Hull menggunakan algoritma Divide and Conquer. Dimana permasalahan Convex Hull adalah suatu permasalahan yang terdiri dari aplikasi terapan yang lumayan banyak, misalnya pada permasalahan grafika komputer, otomasi desain, pattern recognition (pengenalan pola), juga penelitian operasi.
3. Persoalan minimum dan maksimum atau MinMax.
4. Optimasi konversi bilangan dari bilangan desimal ke bilangan biner.
5. Mencari pasangan dari titik yang jaraknya dekat atau close pair.

Implementasi Algoritma Divide and Conquer

Di bawah ini merupakan implementasi algoritma Divide and Conquer:

Implementasi Algoritma Divide and Conquer Insertion Sort

Insertion sort adalah salah satu algoritma sorting yang termasuk paling sederhana. Analogi dari ide algoritma ini seperti dalam mengurutkan kartu. Penjelasan dari cara kerjanya algoritma insertion sort dalam pengurutan kartu adalah seperti berikut ini:

Misalnya, ketika anda ingin mengurutkan satu set kartu mulai dari kartu yang nilainya paling kecil sampai yang nilainya paling besar. Maka seluruh kartu akan diletakkan pada sebuah meja. Katakanlah diletakkan pada meja pertama. Lalu disusun dengan susunan dari kiri ke kanan dan dari atas ke bawah. Selanjutnya siapkan meja lain, atau meja kedua, untuk meletakkan kartu yang diurutkan.

Untuk mengurutkan satu set kartu tersebut tentu akan mengikuti langkah-langkah berikut:

• Ambil kartu pertama dari pojok kiri atas di meja pertama, lalu letakkan pada meja kedua
• Lalu ambil kartu yang kedua kedua dari meja pertama
• Selanjutnya bandingkan dengan kartu yang berada di meja kedua
• Setelah melakukan perbandingan, letakkan kartu kedua tersebut pada urutan yang sesuai di meja kedua
• Proses seperti itu akan berlangsung hingga seluruh kartu yang diletakkan pada meja pertama telah berhasil diletakkan berurutan pada meja kedua

Pada dasarnya algoritma insertion sort ini memilah data yang akan diurutkan tersebut menjadi dua bagian, yaitu bagian yang belum diurutkan terletak pada meja pertama, dan bagian yang sudah diurutkan pada meja kedua. Elemen pertamanya diambil dari bagian array yang masih belum diurutkan, lalu diletakkan sesuai posisinya pada bagian lain array yang sudah diurutkan. Langkah seperti itu dilakukan secara berulang sampai semua elemen yang belum diurutkan tidak tersisa. Dapat dilihat seperti pada gambar di bawah ini: