Introduction to Divide and Conquer
There are many computer science topics that revolve around this algorithm. This technique has been used in various famous algorithms which are discussed further. To become a good problem solver, One must be aware of this topic and also learn to apply it whenever required in obtaining the solution in optimised manner.
Divide and Conquer, the name itself indicates that the problem needs to be solved by dividing it into various subproblems and the solution of all these subproblems is combined/merged to obtain the solution for the given problem. Divide and conquer is an important topic to be understood and used during problem-solving to avoid Time Limit Errors and also to solve the given problem in optimized time complexity for the given question.
How does the divide and conquer technique work?
In the above section, we have discussed what divide and conquer is and why it is so important in problem-solving. Now let's talk about the implementation part of this technique. Everyone gets stuck due to poor understanding, but it's not very typical. It basically revolves around the words like dividing the given complex problem into smaller easily solved subproblems from which we merge the results of these sub-problems and obtain the solution for the given question. Following this principle, in the divide and conquer algorithm, we keep dividing the given problem into smaller problems to the point that these smaller subproblems can no longer be further divided, that is we will reach the atomic level. This can be better explained by the below image.
Here let's discuss the example of the divide and conquer algorithm to get a better understanding of the topic. We will be discussing the prominent Merge Sort algorithm.
Lets the example of the array names as arr as:
arr=[1,3,2,8,5,7,4,0]
The given examples consist of 8 elements ie n (length of the array )=8 and they are divided exactly into two equal parts by calculating mid position and split according to it.
mid =(len(arr))/2
So, in m=4
Explaining different stages in this Algorithm
Divide: Each sub-array is divided into two halves while calculating mid till it reaches the position where it cannot be divided into halves, ie till we reach one element.
This is a brief explanation of the DIVIDE stage in the algorithm.
Let's look at the below image to get a better understanding of each stage in the divide and conquer technique.
The above image it is clearly indicating that the given complex problem is divided into further sub-problems by calculating the midpoint recursively and reaching the atomic stage at the end. Now let's discuss the second individual stage i.e, the Conquer stage.
Conquer: This is the intermediary step within the divide and conquers problem-solving approach, where all the individual atomic sub-problems are solved and their solutions are obtained. These obtained solutions are merged in the next stage. In this step, each block of elements is sorted individually.
Combining/Merging: This is a crucial step in this approach to obtain the solution for the given problem. We need to merge all these solutions from subproblems and combine them to get a solution for our real problem. This is also done recursively. Finally, we arrive at the merge stage of the merge sort algorithm. Here, we will recursively combine the subarrays in a sorted manner until we are left with just one array. ie the solution to the given problem
Here’s how the merging is done. We take two sorted subarrays, and with a pointer at the left(P1, P2) end of both the subarrays. We keep adding whichever value is the smallest, to the solution array and hence incrementing the pointers until all the elements in both the subarrays are traversed. This technique is generally called Two pointer technique, to sort the arrays.
At each step in the dividing stage, the problem is divided into 2 equal halves, therefore the time complexity to obtain will be log(n), where n is the length of the array. At the merge step, it takes about n time to recursively merge all subarrays, So, the total time complexity reaches about O(n log(n)). Here we can say that compared to other sorting algorithms(Bubble, insertion sort, etc), the quadratic O(n^2) is reduced to O(n log(n)).
We observe that each stage is using recursion to attain its purpose. For a better understanding of the divide and conquer algorithms the prerequisite is Recursion. They both go hand in hand. Let's get into the next section to explore more about the applications of the Divide and Conquer technique.
Applications of Divide and Conquer
There are various applications of this prominent technique, but very few and important as well as very useful algorithms, which combine this technique will be discussed now.
- Merge sort: Earlier we discussed more this algorithm.
- Quick Sort: This sorting technique also uses divide and conquer by dividing the array using pivot elements and further combining the sorted subarrays to obtain the solution.
- Dynamic Approach ( ie used in Dynamic Programming): In Various DP questions, we use the divide and conquer technique, we can store the results of sub-problems, whereas, in other algorithms, we don't do that.
- Binary search: This searching technique is applied to a sorted list of elements, wherein each step is divided into halves to obtain the solution in O(log(n)) rather than in O(n) like in the Linear Search Algorithm.
Conclusion
With this, we have come to an end with the divide and conquer algorithm, where the given problem is divided into various sub-problems and the solutions of these sub-problems are combined to get the solution to the complex problem. In this article, we have discussed a very useful Merge Sort and various applications of Divide and Conquer.