Mastering Divide and Conquer Algorithms with Java
SANTOSH SINGH
Introduction
Divide and conquer is a powerful algorithmic paradigm that forms the backbone of many efficient algorithms. By breaking a problem into smaller subproblems, solving them independently, and then combining their solutions, divide and conquer can significantly reduce the time complexity of a problem. In this blog, we'll explore the divide and conquer approach, focusing on its implementation in Java, with a step-by-step guide and examples.
What is Divide and Conquer?
Divide and conquer is an algorithmic strategy that involves three main steps:
Divide: Break the problem into smaller subproblems that are similar to the original problem but smaller in size.
Conquer: Solve the subproblems recursively. If the subproblem size is small enough, solve it directly.
Combine: Merge the solutions of the subproblems to get the solution to the original problem.
This approach is particularly effective for problems that can be divided into independent subproblems, such as sorting, searching, and matrix multiplication.
Classic Examples of Divide and Conquer
- Merge Sort
Merge Sort is a classic example of divide and conquer. It works by splitting an array into two halves, recursively sorting each half, and then merging the sorted halves.
public class MergeSort {
public void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int 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++;
}
}
public void sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
- Quick Sort
Quick Sort is another divide and conquer algorithm. It picks a pivot element, partitions the array around the pivot, and recursively sorts the subarrays.
public class QuickSort {
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;
}
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
- Binary Search
Binary Search is one of the simplest and most efficient examples of the divide and conquer technique. It works on sorted arrays by repeatedly dividing the search interval in half.
public class BinarySearch {
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
// Check if the element is present at the middle
if (arr[mid] == x)
return mid;
// If the element is smaller than mid, it can only be in the left subarray
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
// Otherwise, it can only be in the right subarray
return binarySearch(arr, mid + 1, right, x);
}
// If the element is not present in the array
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {2, 3, 4, 10, 40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
- Strassen's Matrix Multiplication
Strassen's algorithm is an improvement over the standard matrix multiplication technique. It reduces the number of multiplications needed and is an excellent example of divide and conquer applied to matrix operations.
public class Strassen {
public int[][] multiply(int[][] A, int[][] B) {
int n = A.length;
int[][] C = new int[n][n];
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
} else {
int[][] A11 = new int[n / 2][n / 2];
int[][] A12 = new int[n / 2][n / 2];
int[][] A21 = new int[n / 2][n / 2];
int[][] A22 = new int[n / 2][n / 2];
int[][] B11 = new int[n / 2][n / 2];
int[][] B12 = new int[n / 2][n / 2];
int[][] B21 = new int[n / 2][n / 2];
int[][] B22 = new int[n / 2][n / 2];
divide(A, A11, 0, 0);
divide(A, A12, 0, n / 2);
divide(A, A21, n / 2, 0);
divide(A, A22, n / 2, n / 2);
divide(B, B11, 0, 0);
divide(B, B12, 0, n / 2);
divide(B, B21, n / 2, 0);
divide(B, B22, n / 2, n / 2);
int[][] M1 = multiply(add(A11, A22), add(B11, B22));
int[][] M2 = multiply(add(A21, A22), B11);
int[][] M3 = multiply(A11, subtract(B12, B22));
int[][] M4 = multiply(A22, subtract(B21, B11));
int[][] M5 = multiply(add(A11, A12), B22);
int[][] M6 = multiply(subtract(A21, A11), add(B11, B12));
int[][] M7 = multiply(subtract(A12, A22), add(B21, B22));
int[][] C11 = add(subtract(add(M1, M4), M5), M7);
int[][] C12 = add(M3, M5);
int[][] C21 = add(M2, M4);
int[][] C22 = add(subtract(add(M1, M3), M2), M6);
join(C11, C, 0, 0);
join(C12, C, 0, n / 2);
join(C21, C, n / 2, 0);
join(C22, C, n / 2, n / 2);
}
return C;
}
public void divide(int[][] P, int[][] C, int iB, int jB) {
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
for (int j1 = 0, j2 = jB; j1 < C.length; j
1++, j2++)
C[i1][j1] = P[i2][j2];
}
public int[][] add(int[][] A, int[][] B) {
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j];
return C;
}
public int[][] subtract(int[][] A, int[][] B) {
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
C[i][j] = A[i][j] - B[i][j];
return C;
}
public void join(int[][] C, int[][] P, int iB, int jB) {
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)
for (int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)
P[i2][j2] = C[i1][j1];
}
public static void main(String[] args) {
Strassen s = new Strassen();
int[][] A = {{1, 2}, {3, 4}};
int[][] B = {{5, 6}, {7, 8}};
int[][] C = s.multiply(A, B);
System.out.println("Result matrix:");
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < C[0].length; j++) {
System.out.print(C[i][j] + " ");
}
System.out.println();
}
}
}
- Maximum Subarray Problem (Kadane’s Algorithm via Divide and Conquer)
The Maximum Subarray Problem involves finding the subarray with the maximum sum within a given array of integers. The divide and conquer solution breaks the array into subarrays and finds the maximum subarray that crosses the midpoint.
public class MaxSubArray {
int maxCrossingSum(int arr[], int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = mid; i >= left; i--) {
sum += arr[i];
if (sum > leftSum)
leftSum = sum;
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
if (sum > rightSum)
rightSum = sum;
}
return leftSum + rightSum;
}
int maxSubArraySum(int arr[], int left, int right) {
if (left == right)
return arr[left];
int mid = (left + right) / 2;
return Math.max(
Math.max(maxSubArraySum(arr, left, mid),
maxSubArraySum(arr, mid + 1, right)),
maxCrossingSum(arr, left, mid, right)
);
}
public static void main(String[] args) {
MaxSubArray ob = new MaxSubArray();
int arr[] = {2, 3, 4, 5, 7};
int n = arr.length;
int maxSum = ob.maxSubArraySum(arr, 0, n - 1);
System.out.println("Maximum contiguous sum is " + maxSum);
}
}
Conclusion
The divide and conquer approach is not just limited to sorting algorithms but extends to various complex problems like matrix multiplication, searching, and even dynamic programming problems like the maximum subarray problem. Understanding and applying divide and conquer helps in breaking down complex problems into manageable subproblems, leading to efficient solutions.
Subscribe to my newsletter
Read articles from SANTOSH SINGH directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by