A Gentle Introduction of Divide and Conquer Algorithm

A Gentle Introduction of Divide and Conquer Algorithm

3 mins read511 Views Comment
Updated on Dec 27, 2023 18:06 IST

The divide and Conquer algorithm first divide the problem and then conquers or solves it. This article will briefly discuss about the algorithm, its working, and properties of algorithms. Let's understand more!

2022_12_MicrosoftTeams-image-102-2.jpg

The goal of data structure and algorithm is to organize the data in an optimized and efficient manner so that it can be retrieved easily. Data structure mainly uses three approaches to solve any problem or to find a quick solution to any problem; those three approaches are:

  • Divide & Conquer
  • Greedy Algorithm 
  • Dynamic Programming. 

In Divide and Conquer methodology, the main problem is divided into sub-problems, and those sub-problems are further divided until we get a unitary subproblem that can be solved. After finding the solution to the unitary sub-problems and combining these solutions, the main problem can be solved. 

The greedy algorithm approach works the same as its name suggests; the algorithm always selects the solution with the least cost in every iteration. 

Dynamic programming is the methodology in which each problem is divided into sub-problems and solved; when the problem cannot be subdivided further, it is solved, and the solution is stored. The idea behind storing the solution is to reuse it whenever the same problem function is encountered instead of solving it again. 

This article will discuss the divide and conquer programming paradigm, the working of divide and conquer, algorithms using divide and conquer, and applications of the divide and conquer mechanism. 

Table of Content

What is Divide and Conquer Algorithm

As the name suggests, the divide and conquer algorithm first divides the problem and then conquers or solves it. The divide-and-conquer algorithmic paradigm is divided into three parts:

Divide: This is the very first step, which involves dividing problems into multiple sub-problems.

Solve/Conquer: This is the second step of the DAC algorithm, and it involves solving each subproblem by calling them recursively until all problems aren’t solved.

Combine: At last, combining the solution of all the sub-problems to give calculate the final solution of the whole problem.

All these steps can be understood easily with the following diagram:

In the above diagram, a problem is divided into two subproblems, and then each subproblem is solved; after solving the problems, we combine their solution to get the final solution.

Working on Divide and Conquer Algorithm

After understanding the concept of the divide and conquer algorithm, let’s understand how the algorithm works. The divide and conquer algorithm is used in various problem-solving techniques. Here we will take an example and sort the array using divide-and-conquer programming paradigms. 

Example: Consider the following array and sort it using the divide and conquer strategy. 

Array: 8 5 1 6 4 2 3 7

Solution: We use merge sort to implement the divide and conquer approach. 

Step 1:

Step 2:

Choose the pivot element and divide the array. Here we choose the middle element as the pivot element and divide the array. 

Step 3:

Further dividing the array into sub-array

Step 4:

Dividing the array recursively until the unitary sub-problem is received.

Step 5:

Now, we have all elements in the unit; we can combine them.

 

Pseudo Code for Divide and Conquer

The Pseudo Code for the divide and conquer algorithm is as follows:


 
DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
m = divide(a, i, j)
b = DAC(a, i, mid)
c = DAC(a, mid+1, j)
d = combine(b, c)
return(d)
}
Copy code

Code for Divide and Conquer


 
int main()
{
int ar[] = {8, 5, 1, 6, 4, 2, 3, 7};
int ar_size = sizeof(ar) / sizeof(ar[0]);
printf("Given array: \n");
printArray(ar, ar_size);
mergeSort(ar, 0, ar_size - 1);
printf("\n The Sorted array: \n");
printArray(ar, ar_size);
return 0;
}
#include
#include
void merge(int ar[], int l, int m, int r)
{
int i, j, k;
int x = m - l + 1;
int y = r - m;
/* create temporary arrays */
int L[x], R[y];
/* Copy data to temporary arrays (left and right)L[] and R[] */
for (i = 0; i < x; i++)
L[i] = ar[l + i];
for (j = 0; j < y; j++)
R[j] = ar[m + 1 + j];
/* Merge the temporary arrays back into ar[l..r]*/
i = 0; // First subarray’s initial index
j = 0; // Second subarray’s initial index
k = l; // Merged subarray’s initial index
while (i < x && j < y) {
if (L[i] <= R[j]) {
ar[k] = L[i];
i++;
}
else {
ar[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there
are any */
while (i < x) {
ar[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[] */
while (j < y) {
ar[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array ar to be sorted */
void mergeSort(int ar[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(ar, l, m);
mergeSort(ar, m + 1, r);
merge(ar, l, m, r);
}
}
/* Function to print */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
Copy code

Properties of Divide and Conquer Algorithm

  • The divide and conquer programming approach reduces or simplifies the time complexity of the algorithms like it can affect computer multiplication of two algorithms in O(n(2.8074)) whereas it takes O (n3) using the naive method. 
  • The perfect approach for multiprocessing systems
  • Makes use of memory caches efficiently. 

Selection Sort Algorithm in C
Selection Sort Algorithm in C
Ever wondered how your favorite music app arranges songs from least to most played, or how an online store lists products from cheapest to priciest? At the heart of such...read more

Bubble Sort Algorithm (With Code)
Bubble Sort Algorithm (With Code)
In today’s world of continuous data generation, it is of utmost importance for all businesses to sort data linearly and attain relationships on the same. With different types...read more

Heap Sort Code in C: What is and Program
Heap Sort Code in C: What is and Program
Heap sort refers to a comparison-based sorting technique that is based on the Binary Heap Data Structure. It creates a heap from input array and sorts the array by using...read more

Quick Sort in C
Quick Sort in C
Have you ever wondered how large datasets are sorted efficiently in programming? Quick Sort in C is the answer, utilizing a divide-and-conquer strategy to sort arrays rapidly by partitioning them...read more

Merge Sort Algorithm (With Code)
Merge Sort Algorithm (With Code)
Merge Sort Algorithm is one of the sorting algorithm similar to selection sort, insertion sort, quick sort algorithms. In this article, we will briefly discuss merge sort algorithm and its...read more

Conclusion

In this article, we have briefly discussed Divide and Conquer Algorithm with the help of examples. We also discussed how divide and conquer algorithms works and its properties.

Hope you will like the article.

Contributed By: Kanika Joshi

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio