Is this correct algorithm that follows divide and conquer technique

[srinivasan106]

this program is to find maximum and minimum using divide and conquer technique

int min=32000,max=0;
void maxi(int [],int,int),merge(int [],int,int,int,int);
void main()
{
	int a[30],n,i;
	printf("enter the limit\n");
	scanf("%d",&n);
	printf("enter the aray elements\n");
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	maxi(a,0,n-1);
	printf("maximum is %d and minimum is %d\n",max,min);
	getch();
}
void maxi(int a[],int first,int last)
{
	int mid=(first+last)/2;
	if(first+1<last)
	{
		maxi(a,first,mid);
		maxi(a,mid+1,last);
		merge(a,first,mid,mid+1,last);
	}
}
void merge(int a[],int f1,int l1,int f2,int l2)
{
	int m1,m2,mi1,mi2;

	/*	max1=a[f1];
	min1=a[f1];
	for(i=f1+1;i<l1;i++)
	{
		if(max1<a[i])
			max1=a[i];
		else if(min1>a[i])
			min1=a[i];
	}*/
	if(a[f1]>a[l1])
	{
		m1=a[f1];
		mi1=a[l1];
	}
	else
	{
		m1=a[l1];
		mi1=a[f1];
	}
	if(a[f2]>a[l2])
	{
		m2=a[f2];
		mi2=a[l2];
	}
	else
	{
		m2=a[l2];
		mi2=a[f2];
	}
	if(m1>max || m2>max)
	{
		if(m1<m2)
			max=m2;
		else
			max=m1;
	}
	if(mi1<min || mi2<min)
	{
		if(mi1<mi2)
			min=mi1;
		else
			min=mi2;
	}
}

THE PROGRAM IS CAPABLE TO FIND THE MAXIMUM AND MINIMUM BUT IS THIS FOLLOWS CORRECT ALGORITHM OF DIVIDE AND CONQUER???.Usually divide and conquer technique provides us a complexity less than usual technique.. can anyone explain how d above code s efficient than d usual code to find the maximum and minimum

[Adak]

I don't like your algorithm, nor do I see anything "divide and conquer", about it.

Try this:

1) take in all the numbers of the array, then
2) use Quicksort to sort the array

Quicksort is a *brilliant* example of a divide and conquer algorithm.

[[Alpha]-0mega-]

QuickSort!

Turns out someone posted a quicksort snippet on the daniweb snippets section.

[srinivasan106]

I don't like your algorithm, nor do I see anything "divide and conquer", about it.

Try this:

1) take in all the numbers of the array, then
2) use Quicksort to sort the array

Quicksort is a *brilliant* example of a divide and conquer algorithm.

i dont want to use any sorting algorithm for finding out the minimum and maximum.
simply divide the arry into sub array and find max min in each sub array and merge it and find the maximum and minimum for the whole array

[srinivasan106]

I don't like your algorithm, nor do I see anything "divide and conquer", about it.

Try this:

1) take in all the numbers of the array, then
2) use Quicksort to sort the array

Quicksort is a *brilliant* example of a divide and conquer algorithm.

isnt 20 and 21 line of my code indicate divide and conquer?? (inside the function maxi)

[tesuji]

Hello srinivasan,

below little code uses recursively called functions to determine min/max of an integer sequence. It works quicksort-like. I am not sure whether this is a useful solution to your problem.

int mini(int n, int ar[])
{
   int ml, mr, nh = n / 2;
   if( n == 1 ) return ar[0];
   ml = mini(nh, ar); mr = mini(n - nh, ar + nh);
   if ( ml < mr ) return ml; else return mr;
}
int maxi(int n, int ar[])
{
   int ml, mr, nh = n / 2;
   if(n == 1) return ar[0];
   ml = maxi(nh, ar); mr = maxi(n - nh, ar + nh);
   if ( ml > mr ) return ml; else return mr;
}
int mima()
{
   int ar[] = {10, 6, 9, -99, 99, 999, -98, 998, -10} ;
   cout << "min: " << mini(9, ar) << "  max: " << maxi(9, ar) << endl;   
   // min: -99  max: 999
   return 0;
}

try it, it should function.

Why do you need an additional merge function?

-- tesu

[srinivasan106]

hello srinivasan,

below little code uses recursively called functions to determine min/max of an integer sequence. It works quicksort-like. I am not sure whether this is a useful solution to your problem.

int mini(int n, int ar[])
{
   int ml, mr, nh = n / 2;
   if( n == 1 ) return ar[0];
   ml = mini(nh, ar); mr = mini(n - nh, ar + nh);
   if ( ml < mr ) return ml; else return mr;
}
int maxi(int n, int ar[])
{
   int ml, mr, nh = n / 2;
   if(n == 1) return ar[0];
   ml = maxi(nh, ar); mr = maxi(n - nh, ar + nh);
   if ( ml > mr ) return ml; else return mr;
}
int mima()
{
   int ar[] = {10, 6, 9, -99, 99, 999, -98, 998, -10} ;
   cout << "min: " << mini(9, ar) << "  max: " << maxi(9, ar) << endl;   
   // min: -99  max: 999
   return 0;
}

try it, it should function.

Why do you need an additional merge function?

-- tesu

actually ur code is recursive.. I want to implement divide and conquer using recursion.. My maxi function divides the problem into sub problems and then find the maximum and minimum for that sub problem... In the merge function am combining all the sub solutions obtained and thus am able to get a maximum and minimum for the given problem...

[tesuji]

actually ur code is recursive.. I want to implement divide and conquer using recursion.. My maxi function divides the problem into sub problems and then find the maximum and minimum for that sub problem... In the merge function am combining all the sub solutions obtained and thus am able to get a maximum and minimum for the given problem...

Oh I see, thank you so much for teaching me that my algorithm is not "the correct algorithm that follows divide and conquer technique"!

I have only divided twice and actually forgotten to conquer. So I say sorry for this slip-up.

-- tesu

[srinivasan106]

Oh I see, thank you so much for teaching me that my algorithm is not "the correct algorithm that follows divide and conquer technique"!

I have only divided twice and actually forgotten to conquer. So I say sorry for this slip-up.

-- tesu

can u explain me hw my code is efficient than usual method to find the maximum and minimum???

[ananda2007]

This is Straight forward maximum and minimim code

#include<iostream.h>
#include<conio.h>
int array[15];
void StraightMaxMin(int n)
{
     int max,min;
     max=min=array[1];
     for(int i=2;i<=n;i++)
     {
             if(array[i]>max)
             max=array[i];
             if(array[i]<min)
             min=array[i];
             }
     cout<<endl<<"Maximum :"<<max;
     cout<<endl<<"Minimum :"<<min<<endl;
}

int main()
{
    
    for(int i=1;i<=15;i++)
    {
            array[i]=rand();
            }
    for(int j=1;j<=15;j++)
    {
            cout<<array[j]<<" ";
            }
    StraightMaxMin(15);
    system("PAUSE");
    return 0;
}


And this recursively maximum and minimim code

#include<stdio.h>
#include<conio.h>
#include <dos.h>
#include<stdlib.h>

int n=15;

int maxmin(int a[],int left, int right, int &max, int &min)
{
int max1,min1,mid;
if(left==right)
max=min=a[left];

else if(left==right-1)
{
if( a[left]>a[right])
	 {
	max=a[left];
	min=a[right];
	}
else
{
max=a[right];
min=a[left];
}
}
else
{
mid=(left+right)/2;
maxmin(a,left,mid,max,min);
maxmin(a,mid+1,right,max1,min1);

	if(max1>max)
	max=max1;
	if(min1<min)
	min=min1;
}
return 0;
 }
 int main()
{
 int a[n],i,max,min;

 for(i=0;i<n;i++)
 {
                  a[i]=rand();
                  }
 for(int j=0;j<n;j++)
 {
         printf("%d ",a[j]);
         }
 maxmin(a,0,n-1,max,min);
 printf("\n Maximum=%d",max);
 printf("\n Minimum=%d",min);
 getch();
	return 0;
 }

Both code are flow Divide & Conquer mathod