Divide and conquer algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

The Divide and Conquer algorithm (also called the Divide and Conquer method) is a basis for many popular sorting algorithms. An algorithm is simply a series of steps to solve a problem. The general idea of divide and conquer is to take a problem and break it apart into smaller problems that are easier to solve.

This idea can be seen in many popular algorithms. A helpful way to think of this idea, would be when a person looks through a dictionary. For example, if they are looking for the word “Dog”, and land on a page with the word “Firetruck”, the person knows that all the pages to the right of firetruck will not contain dog. They know this because D comes before F in the alphabet. This logic allows a person to spend less time searching, because every time they arrive on a page with the wrong letter, they know that they can eliminate the pages to their right or their left. This is an example of diving a problem up into smaller pieces. If one were to apply this concept in programming, one might start with an ordered list. If they wanted to search through that list, they would start near the center of that list. Simple logic would determine if the desired element is to the right or the left of the middle element, or in some cases it may even be the middle element. From there, each time this algorithm searches, it decreases the size of the list by half. This makes searching through the list extremely efficient.