Divide and Conquer Algorithms

In the TRIVIAL SORTING ALGORITHM series, we have seen some sorting algorithms that solve the problem of sorting for the given constraints. We found our solution by analysing Selection sortInsertion Sort and Shell sort. But what if we didn't have those constraints? What if we had access to sufficient amount of RAM and stack space? In such cases, should we stick to our solution from the first series i.e. shell sort? or move ahead to find a new solution that can give us better performance even if the sample size is very large?

'Divide and Conquer' written in a text-book

(Image Credits)

To find an answer to this question, in this series, we will examine an algorithm paradigm called 'Divide and Conquer' (also called TOP-DOWN approach) that enables us to solve many complex problems efficiently; in this case, the sorting problem. First of all, what is 'Divide and Conquer' (D&C)? It surely sounds like some war or a political tactic! It does take its basic idea from the same realms, but in the programming environment, we define it as follows:

Divide the original problem to two or more than two sub-problems of the same or similar type, having small size and then solve these small sub-problems recursively (apply D&C on each of them if solution is not direct) and once solved, combine the results from sub-problems in such a way that leads to the solution of the original problem.

So Divide and Conquer has the following three simple steps:
1. Divide the problem into sub-problems.
2. Solve the each of the sub-problems recursively.
3. Combine the results of each sub-problem in some logical way to form the overall solution.

Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls. This approach was not conducive to our earlier memory strapped embedded devices and thus, not suitable for our earlier problems. However, now that we've relaxed that constraint on memory, such recursive algorithms could do wonders.

So, in the coming tutorials, we would examine the Merge sort and Quick Sort to see how they use divide and conquer, and analyse their behaviour, performance, pros and cons to solve our sorting problem. We would also see Binary search; though it has nothing to do with sorting, it is a very important technique for finding any element and exhibits the power of divide and conquer.

blog comments powered by Disqus