Question

Below is a linear time complexity algorithm Max-Min-VER1 to find the biggest and smallest element a given list.

Input: A is a given list

Output: two integers

Example: Given A = {1, 5, 9, -3}. It returns -3 (the smallest element), and 9 (the biggest element)

Max-Min-VER1(A, n)

Line 1: large ← A[0]

Line 2: for I from 1 to n - 1 do

Line 3:     large ← Math.max(large, A[I])

Line 4: small ← A[0]

Line 5: for I from 1 to n - 1 do

Line 6:     small ← Math.min(small, A[I])

Line 7: return large and small

• implementation in C++
• Answer the question - How many comparisons are used in the algorithm?

improve above algorithm to decrease the number of comparisons

and Compare both for the time used in milliseconds for running 100 randomly generated lists of each input size 10², 10⁴, and 10⁶.

Answer 1

import java.util.Random;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Vamsi
*/
public class MaxMin {
//finds the max and min in a[]
public static void Max_Min_Ver1(int a[],int n)
{
int large = a[0];
int c=0;//to count comparisions
for(int i=1;i<n;c++,i++)
if(large<a[i])//1 comparision herr
{
large =a[i];
  
}
int small = a[0];
for(int i=1;i<n;c++,i++)
if(a[i]<small)//comparision
{
small = a[i];
  
  
}
System.out.println("Max is :"+large+"\nMin is :"+small+"\nComparisions:"+c);
  
  
}
  
  
//improved method
public static void Max_Min_Ver2(int a[],int n)
{
int large = a[0];
int small = a[0];
int c=0;//to count comparisions
for(int i=1;i<n;c++,i++)
if(large<a[i])//1 comparision here
{
large =a[i];
  
}
else if(a[i]<small)//comparision here
{
small = a[i];
c++;
}
  
  
System.out.println("Max is :"+large+"\nMin is :"+small+"\nComparisions:"+c);
  
  
}
//method to fill array with random numbers
public static void fill(int a[])
{
Random r = new Random();//to generate random numbers
  
for(int i=0;i<a.length;i++)
{
a[i] =r.nextInt()%1000;
  
}
  
  
}
public static void main(String argv[])
{
  
  
//arrays with different sizes
int a[] = new int[102];
int b[] = new int[104];
int c[] = new int[106];
  
  
//testing on 100 different list
  
for(int i=1;i<=1;i++)//change here 1 to 100, to generate 100 different tests
{
System.out.println("Test"+i+"\n");
fill(a);//filling a
System.out.println("Results for array A");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(a,a.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(a,a.length);
System.out.println();
  
fill(b);//filling b
System.out.println("Results for array B");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(b,b.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(b,b.length);
System.out.println();
  
fill(c);//filling c
System.out.println("Results for array C");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(c,c.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(c,c.length);
  
  
System.out.println();
}
  
  
  
  
  
  
}
}

output:

run:
Test1

Results for array A
Max-Min-VER1
Max is :998
Min is :-990
Comparisions:202
Max-Min-VER2
Max is :998
Min is :-990
Comparisions:105

Results for array B
Max-Min-VER1
Max is :997
Min is :-967
Comparisions:206
Max-Min-VER2
Max is :997
Min is :-967
Comparisions:110

Results for array C
Max-Min-VER1
Max is :962
Min is :-991
Comparisions:210
Max-Min-VER2
Max is :962
Min is :-991
Comparisions:108

BUILD SUCCESSFUL (total time: 1 second)

import java.util.Random;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Vamsi
*/
public class MaxMin {
//finds the max and min in a[]
public static void Max_Min_Ver1(int a[],int n)
{
int large = a[0];
int c=0;//to count comparisions
for(int i=1;i<n;c++,i++)
if(large<a[i])//1 comparision herr
{
large =a[i];
  
}
int small = a[0];
for(int i=1;i<n;c++,i++)
if(a[i]<small)//comparision
{
small = a[i];
  
  
}
System.out.println("Max is :"+large+"\nMin is :"+small+"\nComparisions:"+c);
  
  
}
  
  
//improved method
public static void Max_Min_Ver2(int a[],int n)
{
int large = a[0];
int small = a[0];
int c=0;//to count comparisions
for(int i=1;i<n;c++,i++)
if(large<a[i])//1 comparision here
{
large =a[i];
  
}
else if(a[i]<small)//comparision here
{
small = a[i];
c++;
}
  
  
System.out.println("Max is :"+large+"\nMin is :"+small+"\nComparisions:"+c);
  
  
}
//method to fill array with random numbers
public static void fill(int a[])
{
Random r = new Random();//to generate random numbers
  
for(int i=0;i<a.length;i++)
{
a[i] =r.nextInt()%1000;
  
}
  
  
}
public static void main(String argv[])
{
  
  
//arrays with different sizes
int a[] = new int[102];
int b[] = new int[104];
int c[] = new int[106];
  
  
//testing on 100 different list
  
for(int i=1;i<=1;i++)//change here 1 to 100, to generate 100 different tests
{
System.out.println("Test"+i+"\n");
fill(a);//filling a
System.out.println("Results for array A");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(a,a.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(a,a.length);
System.out.println();
  
fill(b);//filling b
System.out.println("Results for array B");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(b,b.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(b,b.length);
System.out.println();
  
fill(c);//filling c
System.out.println("Results for array C");
System.out.println("Max-Min-VER1");
Max_Min_Ver1(c,c.length);
System.out.println("Max-Min-VER2");
Max_Min_Ver2(c,c.length);
  
  
System.out.println();
}
  
  
  
  
  
  
}
}

output:

run:
Test1

Results for array A
Max-Min-VER1
Max is :998
Min is :-990
Comparisions:202
Max-Min-VER2
Max is :998
Min is :-990
Comparisions:105

Results for array B
Max-Min-VER1
Max is :997
Min is :-967
Comparisions:206
Max-Min-VER2
Max is :997
Min is :-967
Comparisions:110

Results for array C
Max-Min-VER1
Max is :962
Min is :-991
Comparisions:210
Max-Min-VER2
Max is :962
Min is :-991
Comparisions:108

BUILD SUCCESSFUL (total time: 1 second)