Divide and Conquer Algorithm
Divide and Conquer Algorithm
Divide and Conquer algorithm consists following three steps.
- Divide: Divide is the the original problem into a subproblems using recursion.
- Conquer: Conquer is to solve every smaller subproblem individually, recursively.
- Combine: Combine is the solutions of the subproblems to get the solution to the actual problem.
Examples of Divide and conquer
The computer algorithms are based on divide-and-conquer programming approach they are follows−
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (points)
Example :
Divide And Conquer algorithm
DC(a, i, j) { if(small(a, i, j)) return(Solution(a, i, j)) else m = divide(a, i, j) // f1 (n) b = DC(a, i, mid) // T(n/2) c = DC(a, mid+1, j) // T(n/2) d = combine(b, c) // f2 (n) return(d) }
Program for Divide and Conquer in C
#include <stdio.h> int DAC_Max(int a[], int index, int l); int DAC_Min(int a[], int index, int l); // function to find the largest no. in a given array. int DC_Max(int a[], int index, int l) { int max; if (index >= l - 2) { if (a[index] > a[index + 1]) return a[index]; else return a[index + 1]; } // find the largest element max = DC_Max(a, index + 1, l); if (a[index] > max) return a[index]; else return max; } // Function to find the smallest no. int DC_Min(int a[], int index, int l) { int min; if (index >= l - 2) { if (a[index] < a[index + 1]) return a[index]; else return a[index + 1]; } // find the Samllest element min = DC_Min(a, index + 1, l); if (a[index] < min) return a[index]; else return min; } //Code int main() { // Defining the variables int min, max, N; // Initializing the array int a[7] = { 75, 260, 60, 95, 150, 15, 10 }; // recursion max = DC_Max(a, 0, 7); // recursion min = DC_Min(a, 0, 7); printf(" smallest no is : %d\n", min); printf(" largest no is : %d", max); return 0; }
Output
samllest no is: 10 lasgest no is: 260
Program for Divide and Conquer in C++
# include<iostream> using namespace std; // find the largest no. int DC_Max(int arr[], int index, int l) { int max; if(index >= l - 2) { if(arr[index] > arr[index + 1]) return arr[index]; else return arr[index + 1]; } max = DC_Max(arr, index + 1, l); if(arr[index] > max) return arr[index]; else return max; } // find the smallest no. int DC_Min(int arr[], int index, int l) { int min; if(index >= l - 2) { if(arr[index] < arr[index + 1]) return arr[index]; else return arr[index + 1]; } min = DC_Min(arr, index + 1, l); if(arr[index] < min) return arr[index]; else return min; } // code int main() { int arr[] = {130, 41, 45, 32, 58, 9, 90}; int n = sizeof(arr) / sizeof(arr[0]); int max, min; max = DC_Max(arr, 0, n); min = DC_Min(arr, 0, n); cout << "largest: " << max << endl; cout << "smallest: " << min << endl; return 0; }
Output
Largest: 130 Smallest: 9
Program for Divide and Conquer in Java
class ABC{ // find the largest no. static int DC_Max(int a[], int index, int l) { int max; if (index >= l - 2) { if (a[index] > a[index + 1]) return a[index]; else return a[index + 1]; } // How to find the Maximum element max = DAC_Max(a, index + 1, l); if (a[index] > max) return a[index]; else return max; / find the samllest no static int DAC_Min(int a[], int index, int l) { int min; if (index >= l - 2) { if (a[index] < a[index + 1]) return a[index]; else return a[index + 1]; } // find the samllest element in the given array. min = DC_Min(a, index + 1, l); if (a[index] < min) return a[index]; else return min; } // Code public static void main(String[] args) { // Defining the variables int min, max; // Initializing the array int a[] = { 70, 250, 50, 80, 140, 12, 14 }; // Recursion max = DC_Max(a, 0, 7); // Recursion min = DC_Min(a, 0, 7); System.out.printf("The smallest number in " + "a given array is : %d\n", min); System.out.printf("The largest number in " + "a given array is : %d", max); } } }
Output
Samllest: 14 Largest: 250
Applications of Divide and Conquer Approach:
Based on the concept of the Divide and Conquer Technique they are follows
- Binary Search
- Quicksort
- Merge Sort
- Closest Pair of Points
- Strassen’s Algorithm
- Cooley-Tukey Fast Fourier Transform (FFT) algorithm
- Karatsuba algorithm for fast multiplication
Advantages of Divide and Conquer
- It is using for Solving difficult problems
- Divide and conquer is used for Parallelism that is to solve the subprblems independently
- It is used to Memory access i.e. it make efficient use of memory caches
Disadvantages of Divide and Conquer
- Divide and conquer approach is that recursion is slow
- Problem decomposition may be very complex and so it not suitable to divide and conquer.
- An explicit stack overuse the space.
Also read, Master theorem