What is Divide and Conquer Algorithm | Learn DSA-1

A Divide and conquer an algorithm is an approach to solving a large problem by breaking the problem into smaller sub-problems, then solving sub-problems, and combining them to get the desired output.

The “Recursion” technique is used in divide and conquer. Click here to learn about recursion.

How Divide and Conquer algorithm work?

This algorithm has three steps: Divide → Conquer → Combine.

1. Divide: Divide the given problem into sub-problems using recursion.
2. Conquer: Solve the smaller sub-problems recursively and If the sub-problem is small enough, then solve it directly.
3. Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.

Example: Sort an Array!

Sort an Array using divide and conquer technique.

Divide and Conquer Implementation:

We will do QuickSort of an array to implement the Divide and Conquer algorithm.

• To write a JavaScript function.
• Input: An array of numbers.
• Output: Sorted array.

For ascending sort: In every loop, we pick a pivot element and put all the elements smaller than the pivot to the left of the pivot element and all greater than the pivot to the right of the pivot element. (Do the reverse for descending sort)