![]() The output of the algorithm will be a sorted array with the values arranged in increasing order.Īs we read earlier, the first step of the algorithm will be to divide the problem at hand into atomic sub-problems. 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. Divide : This step constitutes dividing the problem at hand into smaller, atomic problems. ![]() Let us now take a look into each one of the individual stages of the divide and conquer algorithms, namely : The entire process can be illustrated with the help of the diagram given below : The algorithm then solves these “atoms” individually, and then finally, the solution of all the sub-problems is merged into the final output solution. This stage is known as the atomic state of a problem. The notion here is that it is easier to study (and hence, solve) the smallest unit of a problem than the whole problem altogether.įollowing this principle, in the divide and conquer algorithm, we keep dividing the given problem into smaller problems to the point that these smaller sub-problems can no longer be further divided. ![]() The divide and conquer algorithms work on the principle of atomicity. How Does the Divide and Conquer Algorithm Work?Īs we read earlier, while following the divide and conquer algorithmic approach, one breaks down the given problem at hand into smaller sub-problems, which are then solved individually, before being merged back into the final solution. Let us look at the same in the next section. While the above-given definition gives you a vague idea about what divide and conquer algorithms are, we aim to dive deeper into it and establish a thorough understanding of the subject using this article, where we are going to learn how the divide and conquer algorithms work. The logic behind this is that instead of performing a one-shot solution of a significant, particularly complex problem, it is generally easier to break down the problem into simpler, smaller problems which tend to be easier to solve. One such paradigm in the world of algorithms is known as the “divide and conquer” algorithm.Īs the name itself signifies, the divide and conquer algorithmic approach involves breaking down a given problem into smaller sub-problems, post which these sub-problems are individually solved before being merged again into the output solution. Owing to this fact, there exist thousands of known algorithms in the world of computer science as of now, with the possibility of new additions to this tally always on the table.įor the sake of understanding and studying these algorithms in a generalized, and hence efficient manner, computer scientists have over time developed some classes these algorithms can be grouped under. One of the most peculiar things, when it comes to problem-solving, is that a single problem might have a variety of algorithmic approaches to its solution. Introduction to Divide and Conquer Algorithm It then combines the small solutions to create a complete solution to the original problem statement. Divide and conquer is a paradigm for solving a problem by breaking it up into smaller pieces.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |