Largest and smallest elements of a list

Wh开发者_开发知识库at is the minimum number of comparisons required to find the largest and smallest elements of an unsorted list of n distinct elements?

What could be the best time complexity for above algorithm?

From minimum number of comparisons I meant to specify the most efficient algorithm, for the worst case.

The optimal algorithm takes 3/2*n comparisons.

It works like this:

5 2 6 7 3 1 10 35 4 6

1. [5] [6]
   
2. [5, 2], [6, 4]
   
3. [5, 2, 6], [6, 4, 35]
   
4. [5, 2, 6, 7], [6, 4, 35, 10]
   
5. [5, 2, 6, 7, 1], [6, 4, 35, 10, 3]
   

On each step (n/2) steps, you compare i-th and n-i-th element and move to table "bigger" and "lower"

After n/2 steps, you know, that minimum is in "lower" table and maximum is in "bigger" table. Findin min and max within these two tables is (n/2) * 2, so you have (3/2) * n

It is N * (3/2).

Lower bound (reconstructed from memory; not sure what the cite should be)

Here is an adversary that forces (3/2) n - 2 comparisons when n is even and (3/2) n - 3/2 comparisons when n is odd. The algorithm described by Marcin, when analyzed carefully, achieves these bounds.

Each element is in one of four states: {min, max} (never been compared, so can be the minimum or the maximum), {min} (never been greater than another element, so can be the minimum but not the maximum), {max} (never been less than another element, so can be the maximum but not the maximum), {} (greater than another element, less than another element, can be neither the minimum nor the maximum), where "can be ..." means that there exists a total order compatible with the comparisons performed by the algorithm so far in which ... holds.

Let T be the sum over elements e of the cardinality of e's state. At the beginning, T = 2 n. At the end, T = 2, as otherwise either the minimum or the maximum is not uniquely determined. The following adversary ensures that T decreases by at most 2 with each comparison, and at most 1 unless both elements are being compared for the first time. The stated bounds follow.

The adversary must prevent T from decreasing too quickly while preserving at least one consistent total order. How does the adversary determine the result of a comparison? If neither element is in state {min, max}, then we have it easy. Either the states are different, in which case we resolve according to {min} < {} < {max}, and T stays the same; or they are the same, we give an arbitrary consistent answer, and T decreases by 1. We prove by contradiction that consistency is maintained. Suppose that the most recent comparison creates a cycle. All elements in the cycle now must be in state {}, which is possible only if both were previously in state {}. This contradicts our strategy of answer consistently for elements in the same state.

Otherwise, at least one of the elements being compared is in state {min, max}. If the other is in state {min}, then {min} < {min, max}. If the other is in state {max}, then {min, max} < {max}. Otherwise, resolve arbitrarily. It's clear that T decreases by 2 if and only if the comparison is between two {min, max} elements. This comparison does not create a cycle because the element in state {min, max} has degree 1 in the comparison graph.

It can be done with

3*n/2-2 list element comparisons if n is even
3*(n-1)/2 list element comparisons if n is odd.

Here is the code

minVal = maxVal = a[0];
int i;
for(i = 1; i < n-1; i += 2) {
    if(a[i] < a[i+1]) {
        if(a[i] < minVal)
            minVal = a[i];
        if(a[i+1] > maxVal)
            maxVal = a[i+1];
    }
    else {
        if(a[i+1] < minVal)
            minVal = a[i+1];
        if(a[i] > maxVal)
            maxVal = a[i];
    }
}
// here i == n-1 or i == n
if(i < n) {
    if(a[i] < minVal)
        minVal = a[i];
    else if(a[i] > maxVal)
        maxVal = a[i];
}  

If you're comparing numeric values it can actually be done without any comparisons at all! The trick is to extend the sign bit of the difference between two values and use that as a binary mask.

Perhaps this is more of a clever trick than the "computer sciency" answer you're looking for, but, depending on the compiler and CPU, the following may be faster than the alternatives that use if statements:

void minmax(int values[], size_t count) {
  int min = values[0];
  int max = min;
  for(int i = 1; i < count; ++i) {
    int v = values[i];
    int maxMask = (v - max) >> 31;  // assuming 32-bit int
    max = (max & maxMask) | (v & ~maxMask);
    int minMask = (min - v) >> 31;
    min = (min & minMask) | (v & ~minMask);
  }
  printf("max=%d min=%d\n", max, min);
}

Example call:

int main() {
  int values[] = {
    20, -5, 13, -100, 55
  };
  minmax(values, 5); // prints max=55 min=-10
}

Sum: 0 comparisons, except for the one used by the loop, which can be removed if you unroll the loop :-)

The nice thing with this is that it doesn't use conditional jumps on the machine code level, so there is no risk of pipeline stalls. This algorithm can also easily be extended to compare several values at once (for example eight bytes at once using 64-bit registers).

It's actually somewhere between n-1 and 2(n-1) because you have to compare each element with the current max and min, but if the first comparison returns true, you don't have to do the second one

Nicking the code from the other answer, my solution looks like this:

var largest = list[0];
var smallest = list[0];
for(var i=1;i<list.length;i++)
{
    if(list[i] > largest) {
        largest = list[i];
    } else if(list[i] < smallest) {
        smallest = list[i];
    }
}

If your original list happens to be sorted in ascending order, this code will make n-1 comparisons. If it's sorted in descending order, it will make 2n-2. For all the others it will be somewhere in between.

Here is a good explanation with a working code. Complexity is O( (3n/2) - 2 ).

It also explains the case of odd sized array in which you just do padding.

Use the maxmin algorithm [https://en.wikipedia.org/wiki/Minimax][minmax]

The # of comparisons needed to find the largest and smallest elements of n distinct elements is (3/2)n - 2.

nums is a set of numbers and n(nums) is the number of elements in nums:

minMax (nums) {
   if (n(nums) == 2) {
      nums = {x, y};
      return (max (x, y), min (x, y));   
   }
   else {
      divide nums equally into two sets, set1, set2;
      minMax (set1);
      minMax (set2);
   }
}

I guess it would be (n-1) * 2 as

var largest = list[0];
var smallest = list[0];
foreach(var i in list.Skip(1))
{
  if(i > largest)
      largest = i;
  else if(i < smallest)
      smallest = i;
}