Introduction and brief to Divide and Conquer Algorithms

When we first hear divide and conquer, we automatically understand the ideology behind this algorithm that is pretty self-explanatory. We’ll be taking a look and discussing the two famous divide and conquer algorithms namely- Merge sort and quicksort.

Getting started with a brief about recursion

Starting with the fact that recursion is essential to understand how divide-and-conquer algorithms work. Given below is a video to properly explain to you how recursion works.

What is a divide and conquer algorithm?🤔

Divide and conquer is where you divide a large problem up into many smaller, much easier parts to solve problems and then further combine them into one and getting a solution.

An example below illustrates this.

(this is called merge sort)

In this example, we see an array that has 8 elements and we have to arrange this array in ascending order. Now, these elements keep on further dividing into subgroups of 4 and then 2. After this comparison is done and the elements are arranged in ascending order, they are then further combined into each other into groups of 4 and then back into the array of 8 elements.

How to apply the divide and conquer algorithm approach🧐

The divide and conquer algorithm tries to break a problem down into as many little pieces as possible since it is easier to solve these little pieces and then combine them back to the original problem. It typically does this with recursion.

After Dividing the problem into sub-problems, Conquer the smaller problems by solving them recursively. If the subproblems are small enough, recursion is not needed and you can solve them directly.

Now, let's take an example of how it works.

This is a particular code that uses recursion to find the Factorial of a given number (here taken as 6).

Division

From the above code, we can note some things to be highlighted and pondered upon. The Division of function is at the recursion part. The problem is divided up at return n * recur_factorial(n-1).

The recur_factorial(n-1) part is where the division of the problem takes place.

Conquering

It is the recursion part too, but also the if statement. If the problem is small enough, we can solve it directly (by returning n). Else, we can perform return n * recur_factorial(n-1).

Combining

We do this with the multiplication done inside the function(*). Eventually, we return the factorial of the number as our answer and solution to our problem. This is essentially the crucial end to finally get the main answer otherwise our problem will either keep on running or print 1(the other test case) or will throw an error in the code.

And hence we get our answer as 720 (the factorial of 6).

We’ll explore how the divide-and-conquer works in the famous algorithms that are known as Merge Sort and Quick Sort.

Merge Sort ❗❕

Merge sort is a sorting algorithm based on the divide and conquer technique.

Best-case time complexity- O(n log n)

Worst-case time complexity- O(n log n)

it is one of the most popular and used algorithms.

How to do Merge sort

Step 1 − If it is only one element in the list it is already sorted and make an if condition for it, return the value.
Step 2 − Keep dividing the list recursively into two halves until it can no more be divided.
Step 3 − Now, merge the given smaller lists into a new list in sorted order.

Take a look at this fun video which pictorially describes how merge sort works, You’ll find it interesting ;-)

Quick Sort ❗❕

Quick Sort is another sorting algorithm based on divide-and-conquer.

It picks a pivot from the array (any random element) and divides the given array around that pivot. There are different versions of quickSort that pick pivot in different ways.

Best time complexity-O(n LogN)

Worst time complexity-O(n²)

How to do quicksort

Step 1 − Choose the highest index value that has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − Left element points to the low index
Step 4 − Right element points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step8 − if left ≥ right, the point where they met is the new pivot.

Take a look at another interesting video and see how quicksort is done :-)

Divide and conquer 🆚 Other algorithms and approaches💥

This chart shows the time complexity and space complexity differences between the various sorting algorithms to give you an idea as to where these algorithms stand.

Although the difference arrises when the divide and conquer method is compared with the Greedy approach and Dynamic Programming.

Here are some basic differences for you to understand:-

Conclusion 💠

Divide and conquer algorithms are one of the fast and easier ways to increase the speed of an algorithm. It is essential for a budding developer and programmer to know and understand these concepts of recursion and divide-and-conquer algorithms to solve various problems in his/her path.

Here are the topics we covered in this article:

1. Recursion
2. What is the divide and conquer approach
3. How to apply it
4. Merge sort
5. Quicksort
6. Comparing divide and conquer with the other algorithms and approaches.

That would be all for introduction and brief about what divide and conquer algorithms really are about.