Written by Saikat :
DIVIDE AND CONQUER ALGORITHM:
The most commonly used & convenient algorithm is the 'Divide & conquer' algorithm. If a problem is tough to solve, then we can assume that this problem is made up by some small problems. Then we can break the main problem in some small sub-problems. Now we can easily solve the sub-problems. By this we can solve the whole problem very easily. This method is called Divide and Conquer method. By this method we can also develop efficient programs to solve a particular problem.
STEPS INVOLVED IN THIS ALGORITHM:
1) Divide the total problem into several sub problems of equal length.
2) Obtain the solution of the individual sub problems.
3) Combine the solutions to get the main solution.
ASPECT:
The basic aspect of this algorithm is to minimize the time complexity of a given problem as much as possible. There may be various types of algorithms to solve a particular problem. Among those we shall choose that one, which will take a polynomial order of time complexity, i.e. we will have to choose in such a way that it requires a least number of operations. It will be better if it takes time complexity of linear order.
EXAMPLE:
Take the example of the finding out the maximum and minimum from a set of integers. If we look the overall problem then we will face some challenges. So, just forget the whole problem. Now if there are two numbers then we can easily find out which is smaller and which is bigger by following algorithm.
If(a>b) then MAX <- a and MIN <- b
Else MAX <- b and MIN <- a
This is an easy problem to solve. So, we assume this problem as a unit problem and break the whole problem into sub problems.
Now look at the program and find out what we are doing in it.
#include<stdio.h>
#include<stdlib.h>
int *a;
typedef struct list
{
int min,max;
}ln;
ln minmax(int,int);
int min(int,int);
int max(int,int);
main()
{
int i,n;
ln ext;
printf("Enter the number of element ");
scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("Enter the numbers ");
for(i=0;i<n;i++)
scanf("%d",(a+i));
ext=minmax(0,n-1);
printf("The minmum value is %d and the maximum value is %d",ext.min,ext.max);
return;
}
ln minmax(int n1,int n2)
{
ln ext,ext1,ext2;
if(n2-n1==1)
{
ext.min=min(a[n1],a[n2]);
ext.max=max(a[n1],a[n2]);
return ext;
}
else
{
ext1=minmax(n1,(n1+n2)/2);
ext2=minmax((n1+n2)/2+1,n2);
ext.min=min(ext1.min,ext2.min);
ext.max=max(ext1.max,ext2.max);
return ext;
}
}
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int min(int a, int b)
{
if(a<b)
return a;
else
return b;
}
