Last week I discussed the concept of memoization. This week I wanted to continue discussing concepts needed for dynamic programming and focus on using the method of divide and conqueror.
What Is Divide and Conqueror
Divide and conqueror is an algorithm paradigm based on multi branch recursion. More specifically you take the initial problem and breaking it down into sub-problems until the sub-problems are simple enough to effectively solve. The solutions of the sub-problems are then combined to form the solution of the original problem.
Divide and conqueror is often used to solve problems such as sorting and multiplying large numbers. To show an example I'll show the implementation of merge sort and quick sort. Since I've previously covered these in a post on sorting algorithms this time I've coded them in Ruby!
Remember that these methods are going to be following the following three steps.
- Divide the problem into sub-problems
- Conqueror the sub-problems
- Merge the results of the sub-problems into the final solution
In my implementation I use two functions to clearly illustrate the process of dividing and conqueror. The first method divides the input into smaller arrays that can easily be sorted. The next methods then sorts the smaller arrays and then combines the sorted numbers to return the solution.
In the implementation of quick sort these concepts are also applied in a single method.
Thanks for reading! The code for this lesson can be found here.
Top comments (0)