Divide and conquer is a powerful algorithmic paradigm used to solve complex problems by breaking them down into smaller, more manageable subproblems. Each subproblem is solved independently, and their solutions are combined to form the final solution. This approach is particularly effective for problems that can be recursively divided into smaller subproblems of the same type.
The divide and conquer strategy involves three main steps:
Some classic examples of divide and conquer algorithms include:
Merge Sort is a classic example of the divide and conquer approach. It divides the array into two halves, recursively sorts each half, and then merges the two sorted halves to produce the sorted array.
#include
#include
void merge(std::vector& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector L(n1), R(n2);
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int i = 0; i < n2; ++i)
R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
}
void mergeSort(std::vector& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector arr = {12, 11, 13, 5, 6, 7};
int arr_size = arr.size();
std::cout << "Given array is \n";
for (int i = 0; i < arr_size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
mergeSort(arr, 0, arr_size - 1);
std::cout << "\nSorted array is \n";
for (int i = 0; i < arr_size; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
Quick Sort is another divide and conquer algorithm. It selects a pivot element and partitions the array around the pivot, so that elements less than the pivot are on the left, and elements greater than the pivot are on the right. It then recursively sorts the subarrays.
#include
#include
int partition(std::vector& arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; ++j) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(std::vector& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
std::vector arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
std::cout << "Given array is \n";
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
quickSort(arr, 0, n - 1);
std::cout << "Sorted array is \n";
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
Binary Search is a divide and conquer algorithm used to find an element in a sorted array. It repeatedly divides the array in half, comparing the target value to the middle element.
#include
#include
int binarySearch(const std::vector& arr, int low, int high, int target) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, low, mid - 1, target);
return binarySearch(arr, mid + 1, high, target);
}
return -1;
}
int main() {
std::vector arr = {2, 3, 4, 10, 40};
int target = 10;
int n = arr.size();
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
std::cout << "Element is present at index " << result << std::endl;
else
std::cout << "Element is not present in array" << std::endl;
return 0;
}
Karatsuba Multiplication is an efficient algorithm for multiplying large integers by breaking them into smaller integers.
#include
#include
int karatsuba(int x, int y) {
if (x < 10 || y < 10)
return x * y;
int n = std::max(std::to_string(x).size(), std::to_string(y).size());
int m = n / 2;
int high1 = x / std::pow(10, m);
int low1 = x % static_cast(std::pow(10, m));
int high2 = y / std::pow(10, m);
int low2 = y % static_cast(std::pow(10, m));
int z0 = karatsuba(low1, low2);
int z1 = karatsuba((low1 + high1), (low2 + high2));
int z2 = karatsuba(high1, high2);
return (z2 * std::pow(10, 2 * m)) + ((z1 - z2 - z0) * std::pow(10, m)) + z0;
}
int main() {
int x = 1234;
int y = 5678;
std::cout << "Karatsuba multiplication of " << x << " and " << y << " is " << karatsuba(x, y) << std::endl;
return 0;
}