Question

Programming language: JAVA

First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum element in an unsorted list.

Second, convert your recursive algorithm to a non-recursive (or iterative) implementation. For your input, populate an "unsorted list" with random elements between 1 and 1,000,000.

Answer 1

import java.util.Random;

public class Max_Min {
static int min,max;
//recursive dived and conquer method to find max,min
static void max_min_rec(int a[],int l,int r)
{
if(l==0)
{
max=min=a[l];
}
if(l==r)
{
if(a[l]<min)min=a[l];
if(max<a[l])max=a[l];
  
}
if(l<r){
max_min_rec(a,l,(l+r)/2);
max_min_rec(a,((l+r)/2)+1,r);   
}
}
//iterative method
static void max_min_iter(int a[],int n)
{
max=min=a[0];
for(int i=0;i<n;i++)
{
if(a[i]<min)min=a[i];
if(max<a[i])max=a[i];
}
  
}
public static void main(String argv[])
{
int a[] = new int[10];
Random r = new Random();
for(int i=0;i<10;i++)//generating random numbers between 1,1000000
{ a[i]=r.nextInt()%1000000 +1;
if(a[i]<0)a[i]=a[i]*-1;
}
for(int i=0;i<10;i++)
System.out.print(a[i]+" ");
max_min_rec(a,0,a.length-1);
System.out.println("\nMax:"+max+",Min:"+min);
max_min_iter(a,a.length);
System.out.println("Max:"+max+",Min:"+min);
  
  
}
}

output:

run:
833985 470760 73268 801787 743744 549690 236702 326090 801714 459173
Max:833985,Min:73268
Max:833985,Min:73268
BUILD SUCCESSFUL (total time: 0 seconds)