Guide to Divide and Conquer Algorithms
Today we’re going to cover one of my favorite algorithm design patterns, the divide and conquer algorithm process. There is a very practical reason why divide and conquer algorithms are so popular. And I’m going to discuss those reasons in this guide.
Guide Tasks
  • Read Tutorial
  • Watch Guide Video
Video locked
This video is viewable to users with a Bottega Bootcamp license
APPLY NOWLEARN MORE

What is a Divide and Conquer Algorithm?

Before we can get into the details on what makes divide and conquer algorithms so great, let’s walk through what they are. However I’m going to start with giving a real world example.

A Real World Example of Divide and Conquer

large

In past episodes I’ve explained my process for learning new topics. For example, if I want to learn about logarithms I will go to the logarithm page on Wikipedia. From there I start reading the guide. Each time I get to a topic that I’m unfamiliar with I’ll research the new topic.

After I understand the new topic I’ll go back to the logarithm page and keep reading. I’ll continue this process until I understand what I’m studying.

Essentially I take a divide and conquer approach to learning. I focus on a topic and then break that topic into sub components. After I have a clear understanding of each of the sub topics I typically understand the main topic I was researching.

Dead Simple Divide and Conquer

So here is a dead simple explanation for how divide and conquer algorithms work.

  • They take a problem (such as sorting).
  • Break it into sub tasks.
  • Perform work on each of the sub tasks.
  • End by combining all of the components back together.

Divide and Conquer Code Example

large

If that’s still a little fuzzy, let’s take a look at one of the most popular divide and conquer algorithms in computer science: Quicksort.

Quicksort works by:

  • Taking a collection.
  • Breaking the collection into small pieces.
  • Sorts the small pieces.
  • Combines all of the small pieces into a final, sorted collection.

Benefits to Divide and Conquer Algorithms

There are a number of benefits to using a divide and conquer approach when it comes to algorithm development. Some of the key benefits are:

  • Speed – A well constructed divide and conquer algorithm is typically very fast. For example, the Quicksort algorithm is literally exponentially faster than it’s non divide and conquer alternatives, such as insertion or select sort.
  • Simplifies Complexity – In the same way that I use a similar approach when it comes to learning difficult topics, divide and conquer algorithms can help to simplify a complex task. Many problems in computer science are incredibly challenging when you look at them as a whole. However, if you can break a complex topic down into small, easy to manage chunks, you’ll discover that even difficult problems can be solved… and understood.

List of Divide and Conquer Algorithms

When it comes to getting a job as a developer, you’ll want to have a clear understanding of the popular divide and conquer algorithms. Here is a list of popular algorithms that utilize the divide and conquer approach:

  • Binary Search
  • Quicksort
  • Merge Sort
  • Closest Pair
  • Strassen’s Algorithm

Summary

I hope that this has been a helpful guide to understanding how the divide and conquer algorithm design pattern works. Good luck with the coding!

Resources