We will take a look at merge sort, which is a sorting algorithm based on the divide and conquer approach.įor example, we will be considering the following unsorted array of integers. Now let us further strengthen our understanding of the algorithm with the help of an example. Thus, to establish a strong understanding of the divide and conquer approach, a good understanding of recursion is mandatory. Whether it is breaking down the original problem into sub-problems or merging the individual solutions into the final output, both tasks are done recursively. The output derived after this stage is the required solution for the problem.Īs we can see from the description of the above-mentioned steps, recursion is at the core of the divide-and-conquer algorithms. Merge : Merge constitutes the final stage of the divide and conquers algorithm, where the individual solutions obtained from the previous stage of the algorithm are recursively merged till the solution of the original problem is formulated. However in practice, generally the original problem has already been broken down in the last stage (i.e., the dividing stage) to a level that the sub-problems are considered “solved” on their own. The output of the algorithm, after this step, are atoms of the original problem that can now be worked upon for deriving a solution.Ĭonquer : This is the intermediary step within the divide and conquer problem-solving approach, where in theory, all the individual atomic sub-problems are solved and their solutions are obtained. The divide component of the divide and conquer algorithm follows a recursive approach for breaking down the problem until none of the sub-problems are further divisible. An inherent rule here is that these atoms must be representative of the original problem, which simply implies that these sub-problems have to be a part of the original problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |