List of topics that we cover in the article:
- What is Divide and conquer?
- How problems are solved using Divide and conquer?
- Running times for sorting algorithms.
- Examples of Divide and conquer algorithm.
- Merge sort
- Quick sort
- Binary search
- Strassen’s Matrix multiplication
- Closest Pair
- Implementation of Merge sort.
- Quick sort algorithm.
- Pseudocode for Quicksort.
DIVIDE AND CONQUER ALGORITHM
- What is Divide and Conquer?
Divide and conquer is the most important algorithm in the data structure. The main aim of Divide and conquer is to solve the problem by dividing the complex problem into sub-problems solves in easier manner and later combines all the subproblems to solve the actual problem.
- How problems are solved using divide and conquer?
Usually divide and conquer having the three parts:
Divide: Divide the problem into sub problems.
Conquer: In this step all the sub-problems are solved recursively.
Combine: Here all the subproblems are combined to solve the complex problem.
Running times for sorting algorithm:
- Examples of Divide and conquer:
- Merge sort
- Quick sort
- Implementation of Merge sort:
Merge sort is an example for Divide and conquer algorithm. It is the most important sorting algorithm.
- Merge sort Algorithm:
MergeSort(A, p, r)
In order to sort an array we need to call MergeSort(A,0,length(A)-1)
- Let’s see how the merge sort works:
- create the duplicate copies of subarrays L<-A[p..q] and M <- A[q+1..r]
- create three pointers i,j,k
- i maintains current index of L, starting at 1
- j maintains current index of M, starting at 1
- k maintains current index of A[p..q], starting at p
- select all the larger among the elements from L and M and place them in correct position at A[p..q]
- select the remaining elements and put in A[p..q]
- code looks like:
void merge(int A, int p, int q, int r)
int n1 = q – p + 1;
int n2 = r – q;
int L[n1], M[n2];
for(i = 0; i< n1;i++)
L[i] = A[p+i];
for (j = 0; j<n2;j++)
M[j] = A[q+1+j];
int I, j, k;
I = 0;
J = 0;
K = p;
While (i < n1 && j < n2)
arr[k] = L[i];
arr[k] = M[j];
While (i < n1)
A[k] = L[i];
While (j < n2)
A[k] = M[j];
Merge sort, quick sort, binary search, strassen’s matrix multiplication are the problems that can be solved by Divide and Conquer technique.
For better under understanding lets see one more sorting technique called quick sort.
Quick sort is the most efficient algorithm and divides the array into smaller arrays and choosing one element as pivot the elements which are less than the pivot element placed at left side and the elements which are greater than pivot element placed at right side of the pivot.
Let’s see the implementation of quick sort:
This is how quick sort works.
Quick sort Algorithm:
Make right most index as a pivot value.
Divide the array using pivot value.
Sort the left part of array recursively.
Sort the right part of array recursively.
Quick sort pseudocode:
Procedure quicksort (left, right)
If right-left <= 0
pivot = A[right]
partition = partitionFunc(left, right,pivot)
quicksort (left, partition-1)
quicksort (partition+1, right)
Advantages of quick sort:
- Cache performance is very high when compared to other sorting algorithm.
- No need of extra memory.
Finally, Divide and Conquer algorithm works more efficiently
Take a complex problem to be solved, divide the problem into small sub-problems and solve the sub problems and later combine all the sub-problems to get the solution for the problem this process can be done by recursively.
The important factor in Divide and conquer algorithm is works on multiprocessor system.