Divide and conquer (bagi lalu taklukkan) adalah cara menyelesaikan masalah besar: belah jadi beberapa masalah kecil yang bentuknya sama, selesaikan yang kecil, lalu gabungkan hasilnya. Mirip mengurutkan setumpuk kertas ujian berdua: tumpukannya dibelah dua, tiap orang mengurutkan bagiannya, lalu dua tumpukan rapi itu disatukan. Merge sort, quick sort, dan binary search semuanya memakai pola ini.
🧪 Tebakan cepat: 8 angka yang dibelah dua terus sampai tiap bagian tinggal 1 angka butuh 3 level belahan. Kalau angkanya 16, butuh berapa level: 4, 6, atau 8? Tebak dulu, jawabannya ada di bagian "Kenapa levelnya sedikit".
Tiga langkah: divide, conquer, combine
- Divide: belah masalahnya jadi bagian yang lebih kecil, biasanya jadi dua.
- Conquer: selesaikan tiap bagian. Bagian yang sudah cukup kecil langsung ketahuan jawabannya.
- Combine: gabungkan jawaban bagian-bagian itu jadi jawaban masalah besarnya.
Contohnya, mengurutkan 8 angka dengan merge sort:
| Langkah | Hasilnya |
|---|---|
| Divide | [38, 27, 43, 3] [9, 82, 10, 55] |
| Divide | [38, 27] [43, 3] [9, 82] [10, 55] |
| Divide, lalu conquer | 8 bagian berisi 1 angka, dan 1 angka pasti sudah terurut |
| Combine | [27, 38] [3, 43] [9, 82] [10, 55] |
| Combine | [3, 27, 38, 43] [9, 10, 55, 82] |
| Combine | [3, 9, 10, 27, 38, 43, 55, 82] |
Di kode, divide dan conquer ditulis dengan rekursi: function yang memanggil dirinya sendiri untuk salinan masalah yang lebih kecil. mergeSort untuk 8 angka memanggil mergeSort untuk 4 angka, yang memanggil mergeSort untuk 2 angka, lalu untuk 1 angka. Di situ dia berhenti, karena ada base case: syarat yang langsung dijawab tanpa memanggil dirinya lagi, di sini arr.length <= 1.
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case: 1 angka sudah terurut
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // divide: separuh kiri
const right = mergeSort(arr.slice(mid)); // divide: separuh kanan
return merge(left, right); // combine
}
function merge(left, right) {
const out = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) out.push(left[i++]);
else out.push(right[j++]);
}
return out.concat(left.slice(i), right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]
- Base case ditaruh paling atas, supaya rekursinya pasti berhenti.
midadalah index tengah.arr.slice(0, mid)mengambil separuh kiri,arr.slice(mid)separuh kanan, lalu dua-duanya diurutkan dengan memanggilmergeSortlagi.merge(left, right)adalah combine: menyatukan dua daftar terurut dengan membandingkan angka paling depan masing-masing. Detailnya di pelajaran Merge Sort.
Kenapa levelnya sedikit
Tiap level membelah semua bagian jadi dua. 8 angka butuh 3 level (8, 4, 2, 1). 16 angka cuma butuh 4: datanya dua kali lipat, levelnya cuma nambah satu. Itu jawaban tebakannya. Jumlah level ini disebut log n: 1.000 angka cuma butuh sekitar 10 level.
Kecepatan algoritma ditulis dengan Big-O, yang bilang seberapa cepat kerjanya bertambah kalau datanya bertambah. O(n) artinya datanya dua kali lipat, waktunya kira-kira dua kali lipat. Di merge sort, tiap level combine menyentuh semua n angka sekali, dan ada log n level, jadi totalnya O(n log n): 1.000 angka sekitar 10.000 langkah. Bubble sort butuh sekitar 500.000 perbandingan untuk data yang sama.
Contoh lain: angka terbesar
Mencari angka terbesar di [3, 7, 1, 9, 4] juga bisa dibelah. Separuh kiri [3, 7, 1] punya angka terbesar 7, separuh kanan [9, 4] punya 9. Combine-nya cukup ambil yang lebih besar dari dua jawaban itu: 9.
Binary search juga divide and conquer, bedanya cuma satu separuh yang dikerjakan, separuh lainnya dibuang. Quick sort membelah datanya di sekitar satu angka patokan, lalu mengurutkan dua sisinya.
💡 Kapan bukan divide and conquer? Pola ini paling cocok kalau bagian-bagiannya gak saling bergantung: separuh kiri bisa diurutkan tanpa menunggu separuh kanan. Kalau bagian yang sama dihitung berulang kali, lebih hemat menyimpan hasilnya. Itu dynamic programming, dibahas di pelajaran lain.
⚠️ Jebakan yang sering ketemu
- Base case lupa atau salah. Tanpa
if (arr.length <= 1) return arr;, function memanggil dirinya selamanya, sampai JavaScript menyerah dengan errorMaximum call stack size exceeded. - Masalahnya gak mengecil. Tiap panggilan harus dapat bagian yang lebih kecil.
mergeSort(arr)di dalammergeSort(arr)gak pernah sampai ke base case. - Lupa combine. Mengurutkan dua separuh belum cukup. Tanpa
merge, hasilnya cuma dua potong terurut, bukan satu array terurut.
TL;DR: Divide and conquer punya tiga langkah: divide (belah jadi bagian kecil), conquer (selesaikan tiap bagian, biasanya dengan rekursi), combine (gabungkan hasilnya). Rekursi adalah function yang memanggil dirinya untuk masalah yang lebih kecil, dan base case membuatnya berhenti. Membelah dua terus cuma butuh log n level: data dua kali lipat, levelnya nambah satu. Itu sebabnya merge sort O(n log n).
