WikiGalaxy
Divide and Conquer Technique
Introduction
The Divide and Conquer technique is a powerful algorithm design paradigm based on multi-branched recursion. It involves breaking a problem into smaller sub-problems, solving each sub-problem independently, and then combining their solutions to solve the original problem. This technique is often used in algorithms that require sorting, searching, and solving complex mathematical problems.
Merge Sort
Concept
Merge Sort is a classic example of the Divide and Conquer technique. It divides the unsorted list into two approximately equal halves, sorts each half recursively, and then merges the sorted halves to produce the sorted list.
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Quick Sort
Concept
Quick Sort is another example where the Divide and Conquer technique is utilized. It selects a pivot element, partitions the array around the pivot, and recursively sorts the partitions.
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
Binary Search
Concept
Binary Search is a simple yet effective application of Divide and Conquer. It works on sorted arrays by dividing the search interval in half repeatedly until the target value is found.
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
Strassen's Matrix Multiplication
Concept
Strassen's algorithm for matrix multiplication is a more advanced example of Divide and Conquer. It reduces the number of multiplications needed for matrix multiplication, making it more efficient than the conventional method.
void strassenMultiply(int A[][], int B[][], int C[][], int size) {
// Implementation of Strassen's algorithm
}
Karatsuba Multiplication
Concept
Karatsuba multiplication is an efficient algorithm for multiplying large numbers by breaking them into smaller numbers. It uses the Divide and Conquer approach to reduce the complexity of multiplication.
int karatsuba(int x, int y) {
// Base case for recursion
if (x < 10 || y < 10)
return x * y;
// Calculate the size of the numbers
int n = Math.max(Integer.toString(x).length(), Integer.toString(y).length());
int m = n / 2;
// Split the digit sequences in the middle
int high1 = x / (int) Math.pow(10, m);
int low1 = x % (int) Math.pow(10, m);
int high2 = y / (int) Math.pow(10, m);
int low2 = y % (int) Math.pow(10, m);
// 3 recursive calls made to numbers approximately half the size
int z0 = karatsuba(low1, low2);
int z1 = karatsuba((low1 + high1), (low2 + high2));
int z2 = karatsuba(high1, high2);
return (z2 * (int) Math.pow(10, 2 * m)) + ((z1 - z2 - z0) * (int) Math.pow(10, m)) + z0;
}
