A Gentle Introduction of Divide and Conquer Algorithm
The divide and Conquer algorithm first divide the problem and then conquers or solves it. This article will briefly discuss about the algorithm, its working, and properties of algorithms. Let's understand more!
The goal of data structure and algorithm is to organize the data in an optimized and efficient manner so that it can be retrieved easily. Data structure mainly uses three approaches to solve any problem or to find a quick solution to any problem; those three approaches are:
- Divide & Conquer
- Greedy Algorithm
- Dynamic Programming.
In Divide and Conquer methodology, the main problem is divided into sub-problems, and those sub-problems are further divided until we get a unitary subproblem that can be solved. After finding the solution to the unitary sub-problems and combining these solutions, the main problem can be solved.
The greedy algorithm approach works the same as its name suggests; the algorithm always selects the solution with the least cost in every iteration.
Dynamic programming is the methodology in which each problem is divided into sub-problems and solved; when the problem cannot be subdivided further, it is solved, and the solution is stored. The idea behind storing the solution is to reuse it whenever the same problem function is encountered instead of solving it again.
This article will discuss the divide and conquer programming paradigm, the working of divide and conquer, algorithms using divide and conquer, and applications of the divide and conquer mechanism.
Table of Content
Best-suited Programming courses for you
Learn Programming with these high-rated online courses
What is Divide and Conquer Algorithm
As the name suggests, the divide and conquer algorithm first divides the problem and then conquers or solves it. The divide-and-conquer algorithmic paradigm is divided into three parts:
Divide: This is the very first step, which involves dividing problems into multiple sub-problems.
Solve/Conquer: This is the second step of the DAC algorithm, and it involves solving each subproblem by calling them recursively until all problems aren’t solved.
Combine: At last, combining the solution of all the sub-problems to give calculate the final solution of the whole problem.
All these steps can be understood easily with the following diagram:
In the above diagram, a problem is divided into two subproblems, and then each subproblem is solved; after solving the problems, we combine their solution to get the final solution.
Working on Divide and Conquer Algorithm
After understanding the concept of the divide and conquer algorithm, let’s understand how the algorithm works. The divide and conquer algorithm is used in various problem-solving techniques. Here we will take an example and sort the array using divide-and-conquer programming paradigms.
Example: Consider the following array and sort it using the divide and conquer strategy.
Array: 8 5 1 6 4 2 3 7
Solution: We use merge sort to implement the divide and conquer approach.
Step 1:
Step 2:
Choose the pivot element and divide the array. Here we choose the middle element as the pivot element and divide the array.
Step 3:
Further dividing the array into sub-array
Step 4:
Dividing the array recursively until the unitary sub-problem is received.
Step 5:
Now, we have all elements in the unit; we can combine them.
Pseudo Code for Divide and Conquer
The Pseudo Code for the divide and conquer algorithm is as follows:
DAC(a, i, j){ if(small(a, i, j)) return(Solution(a, i, j)) else m = divide(a, i, j) b = DAC(a, i, mid) c = DAC(a, mid+1, j) d = combine(b, c) return(d)}
Code for Divide and Conquer
int main(){ int ar[] = {8, 5, 1, 6, 4, 2, 3, 7}; int ar_size = sizeof(ar) / sizeof(ar[0]); printf("Given array: \n"); printArray(ar, ar_size); mergeSort(ar, 0, ar_size - 1); printf("\n The Sorted array: \n"); printArray(ar, ar_size); return 0;}
#include #include void merge(int ar[], int l, int m, int r){ int i, j, k; int x = m - l + 1; int y = r - m; /* create temporary arrays */ int L[x], R[y]; /* Copy data to temporary arrays (left and right)L[] and R[] */ for (i = 0; i < x; i++) L[i] = ar[l + i]; for (j = 0; j < y; j++) R[j] = ar[m + 1 + j]; /* Merge the temporary arrays back into ar[l..r]*/ i = 0; // First subarray’s initial index j = 0; // Second subarray’s initial index k = l; // Merged subarray’s initial index while (i < x && j < y) { if (L[i] <= R[j]) { ar[k] = L[i]; i++; } else { ar[k] = R[j]; j++; } k++; } /* Copy the remaining elements of L[], if there are any */ while (i < x) { ar[k] = L[i]; i++; k++; } /* Copy the remaining elements of R[] */ while (j < y) { ar[k] = R[j]; j++; k++; }} /* l is for left index and r is right index of thesub-array ar to be sorted */ void mergeSort(int ar[], int l, int r){ if (l < r) { int m = l + (r - l) / 2; mergeSort(ar, l, m); mergeSort(ar, m + 1, r); merge(ar, l, m, r); }} /* Function to print */ void printArray(int A[], int size){ int i; for (i = 0; i < size; i++) printf("%d ", A[i]); printf("\n");}
Properties of Divide and Conquer Algorithm
- The divide and conquer programming approach reduces or simplifies the time complexity of the algorithms like it can affect computer multiplication of two algorithms in O(n(2.8074)) whereas it takes O (n3) using the naive method.
- The perfect approach for multiprocessing systems
- Makes use of memory caches efficiently.
Conclusion
In this article, we have briefly discussed Divide and Conquer Algorithm with the help of examples. We also discussed how divide and conquer algorithms works and its properties.
Hope you will like the article.
Contributed By: Kanika Joshi
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
