Finding maximum and minimum of an array in a single recursive function

Question

The following program utilizes the Divide and Conquer paradigm and uses the idea of Merge Sort to find the maximum and minimum element of an array recursively. This was an assignment that asked to do it recursively, I've coded the solution but my question is does it minimize the number of comparisons necessary to find the values of a minimum and maximum?

#include <stdio.h>
#include <limits.h>


void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
  //returns the maximum element of the array
  int mid;
  int left, right;

  if(lower == upper){
    if(ptr[lower] > *maximum)
      {
         *maximum = ptr[lower];
      }
    if(ptr[lower] < *min)
      {
         *min = ptr[lower];
      }
    return;
  }

  mid = (lower+upper) /2;

  max(ptr, lower, mid, maximum, min);
  max(ptr, mid+1, upper, maximum, min);
}

int main()
{
  int n;
  int i;

  int *ptr;

  int maximum=-1;
  int minimum=INT_MAX;


  printf("\nEnter the size of the array : ");
  scanf("%d", &n);

  ptr = (int *) malloc(sizeof(int)*n);

  printf("Enter the contents of the array : ");

  for(i=0 ; i<n; i++)
    scanf("%d", &ptr[i]);

  max(ptr,0,n-1,&maximum,&minimum);

  printf("\n Maximum element is : %d", maximum);
  printf("\n Minimum element is : %d", minimum);

  free(ptr);

  return 0;
}

I don't understand - if the array is unsorted, just iterate it. — Martin James
– Martin James, Commented Feb 27, 2016 at 10:19
It was a specific Assignment question to do it recursively. I wrote the above code and it is working correctly, but I can't figure whether it minimizes the number of comparisons or not. Referring to Cormen, the minimum and maximum can be computed in atmost 3* (n/2) . My question is can this bound be satisfied using the above? — kauray
– kauray, Commented Feb 27, 2016 at 10:26
^Kaustabha Roy. It's 3n/2 comparisons. Please be specific in writing — Kevin Pandya
– Kevin Pandya, Commented Feb 27, 2016 at 10:34
@KevinPandya Its 3 * floor(n/2) as mentioned in Cormen, 3n/2 would be for an even 'n' case — kauray
– kauray, Commented Feb 27, 2016 at 11:13

Paolo · Accepted Answer · 2016-02-27 15:46:39Z

does it minimize the number of comparisons necessary to find the values of a minimum and maximum?

Short answer: no

Your code actually requires

n * 4 - 1

comparisons where n is the number of items in the array.

The above counting 1 comparison to check lower==upper and in case it evaluates true 2 more comparisons to check max and min

If you simply parse the array from the beginning to the end with a for loop you'll need

n * 2

comparisons.

But wait: as you also need a for loop at every iteration there is an additional comparison to check if loop ended.

So actually there are

n * 3

comparisons.

The code you posted is not efficient, furthermore you have to calculate mid at each call to max() plus the overhead of recursive function calling.

As you have an unordered array or numbers and you have to find min and max the fastest solution is (as others pointed out) to iterate the array.

If you want a proof you can test it...

Here is the output:

Elements count : 10000
Maximum element is : 99964
Minimum element is : 9
Number of comparisons : 39999

Below is your code with test embedded

(I just added a global g_comparisons that gets incremented before each comparison - also the process of array population is done programmatically with random values)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int g_comparisons = 0;

void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
    //returns the maximum element of the array
    int mid;
    g_comparisons ++;
    if(lower == upper){
        g_comparisons += 2;
        if(ptr[lower] > *maximum)
        {
            *maximum = ptr[lower];
        }
        if(ptr[lower] < *min)
        {
            *min = ptr[lower];
        }
        return;
    }

    mid = (lower+upper) /2;

    max(ptr, lower, mid, maximum, min);
    max(ptr, mid+1, upper, maximum, min);
}

int main()
{
    int n;
    int i;

    int *ptr;

    int maximum=-1;
    int minimum=INT_MAX;


    //printf("\nEnter the size of the array : ");
    //scanf("%d", &n);

    n = 10000;

    ptr = (int *) malloc(sizeof(int)*n);

    // printf("Enter the contents of the array : ");

    for(i=0 ; i<n; i++)
    {
    //    scanf("%d", &ptr[i]);
        ptr[i] = rand()%100000;
    }

    max(ptr,0,n-1,&maximum,&minimum);

    printf("\n Elements count : %d" , n);

    printf("\n Maximum element is : %d", maximum);
    printf("\n Minimum element is : %d", minimum);

    printf("\n Number of comparisons : %d\n", g_comparisons);

    free(ptr);

    return 0;
}

Jean-Baptiste Yunès · Accepted Answer · 2016-02-27 12:57:23Z

2

Use an else to minimize comparisons. If you found a new maximum then it could not be a minimum (or the converse if you want):

if (ptr[lower] > *maximum) {
  *maximum = ptr[lower];
} else {
  if (ptr[lower] < *min) {
    *min = ptr[lower];
}

For this to work, you need to initialize min and max to any value in the array:

minimum = maximum = ptr[0];

Note that in your case, a recursive schema is absolutely unuseful, a simple incremental parsing of the array is sufficient and will let you save a lot of operations (computation of the middle, test of the base case, passing parameters, function calls). An alternative could be to compute your results while scanning the inputs...

edited Feb 27, 2016 at 12:57

answered Feb 27, 2016 at 12:03

Jean-Baptiste Yunès

36.6k4 gold badges51 silver badges76 bronze badges

Comments

Kevin Pandya · Accepted Answer · 2016-02-27 10:46:43Z

0

There are two things I want to point out 1. If the array is sorted then finding minimum and Maximum takes O(1) time. 2. If array is not in sorted order then doing sorting does not help you if your objective is only to find minimum and maximum number. Here is the reason: Any comparison based sorting algorithm takes Ω(nlogn) time whereas maximum and minimum can be found together in a single for loop iteration. By each time comparing next element with the maximum and minimum found so far. So use only one for loop. It will be simple

If your assignment is forcing you to do it recurssively, still it can be done in O(n) comparisons. Simply instead of writing a for loop use a recurssion function with slight modification in the code written in the loop.

edited Feb 27, 2016 at 10:46

answered Feb 27, 2016 at 10:31

Kevin Pandya

1,0961 gold badge9 silver badges12 bronze badges

2 Comments

Martin James Over a year ago

It seems that the OP accidentally forgot to point out that it was an assignment that demanded a recursive solution:(

kauray Over a year ago

I haven't asked for the number of comparisons the above code makes. IF it's O(n) comparisons, is it the best that can be done is my question.

Collectives™ on Stack Overflow

Finding maximum and minimum of an array in a single recursive function

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related