Maximum Algorithm

Sequential examination is not the only way to find the maximum element on a list. Another way to do this is to have the elements play in a tournament much like is done in athletic events. This is accomplished by comparing each pair of elements on the list and moving the largest on to the next round.

Here is the algorithm to do this:

function tournament(a,n)
for i=1 to n do p[i]:=a[i]
k=n (the match list size)
while k>1 do
  { k=k/2
    for i=1 to k do
      if p[2i]>p[2i-1] then p[i]=p[2i]
                       else p[i]=p[2i-1]
   }
return(p[1])


This algorithm works for an even amount of players. I'm trying to make it work for odd number of players and basically make it work for any quantity of players.

What i thought as a solution was to add a random function if the amount of teams is odd. The team selected from the list with this rand will have a bye in the first round. Does this make sense? If it does, where do i put it in algorithm? Any suggestions?
desperadoAsked:
Who is Participating?
 
TEFKASGConnect With a Mentor Commented:
This should look better

function tournament(a,n)
{
   for i=1 to n do p[i]:=a[i]
   k=n (the match list size)

   while (k>1) do
   {
   // if k is odd the last value will not be checked by the general algorithm, so check it here.
      if (k is odd)
      {
      // If the last value is larger then the first value, save it in the first postition
     
         if (p[1] < p[k]) then p[1] = p[k]
      }
// Now do the tournament

 // if the list is odd, the odd end element will be discarded by this division
     k = k/2
     for i=1 to k do
     {
        if p[2i]>p[2i-1] then p[i]=p[2i]
        else p[i]=p[2i-1]
     }
   }
   return p[1]
}
0
 
jhanceCommented:
If the quantity of the members of the list is odd, why not just add a minimum value element to the list?  That way the list is now evenly numbered but the eventual outcome won't be affected.

I guess that is similar to a bye since you're playing a "null" competitor...)
0
 
TEFKASGCommented:
What I would do is at the beginning of the function, if n is odd and greater then 1, do a compare of the first and last values, putting the larger value in the first position, subtract 1 from n then move into your for loop.

 
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
TEFKASGCommented:
Basically you are just evening the teams before you move into your tournament.
0
 
TEFKASGCommented:
Better even the teams inside the while loop prior to k = k/2.  Pseudo code :


while (k > 1) do
{
  if (k is odd)
  {
    if (p[1] < p[k])
       p[1] = p[k];
   }
   k = k/2;
..
..
..
}
return p[1];

 you must compare the last value in the odd numbered list prior to the k/2 division, or the integer divide will round down and the last value will not be compared to any value.  
0
 
desperadoAuthor Commented:
I assume that after k=k/2 goes the missing pseudocode that i copied
0
 
desperadoAuthor Commented:
I still don't understand what youadd exactly does.
0
 
desperadoAuthor Commented:
How is this evening the teams prior to first round:
if(k is odd)
  {
    if (p[1] < p[k])
       p[1] = p[k];
   }
   

0
 
TEFKASGCommented:
After the k/2 goes your code.  
When you divide k by 2, the odd man is automatically discarded, because of the round off of the integer divide. ie if k = 5, k/2 = 2.  In your code the 5th value would not be compared against any element.  The code I added just ensures that the last value is compared against some other value prior to being discarded.

  My first 2 comments were a little off the mark, but I believe my answer to be correct.
0
 
TEFKASGCommented:
The last value is compared and saved if it is larger I meant.
0
 
TEFKASGCommented:
Sorry about the evening teams confusion.  My code doesn't actually even the teams, it just makes sure the odd man out has been checked and saved if it is larger, prior to being left out.
0
 
desperadoAuthor Commented:
You really got me confuse now. What the code you posted do is that it checks for the first element bigger than p[1] and replaces it with it, so the teams are even?
0
 
TEFKASGCommented:
No.  When there are an odd number of elements, my code checks the last(odd) element in the array, and saves it if it is larger than the first element. Then when you divide k by 2 you have two even teams, and the odd element has already been checked correctly.

  Just try it and see if it works.
0
 
desperadoAuthor Commented:
What happens with the numbers in the middle of array. The numbers are not in order. So p[1] can be bigger or smaller than p[k]. But p[k] can be smaller than the other elements if array. What happens if they are equal?
0
 
desperadoAuthor Commented:
The answer he posted did not convince me. how can the while loop that he added to the code I posted solves my problem with the code when teams are not.I wanted to know if there was a way to do this with the rand function in c++.
0
 
TEFKASGCommented:
I did not add a while loop to your code!
I simply added code that will allow your function to work correctly with any number of elements odd or even.

The total code is as follows:


                                    function tournament(a,n)
{
  for i=1 to n do p[i]:=a[i]
    k=n (the match list size)
                                           while k>1 do
  {
      // if k is odd the last value will not be checked by the general algorithm, so check it here.
    if (k is odd)
    {
        // If the last value is larger then the first value, save it in the first postition.                                        
       if (p[1] < p[k])  
         p[1] = p[k];
    }
// Now do the tournament
                                           k=k/2  // the last odd-numbered value is discarded by the integer divide.  
                                           for i=1 to k do
  {                                          if p[2i]>p[2i-1] then p[i]=p[2i]
                   else p[i]=p[2i-1]
  }
                                     
 return(p[1])
}

I don't know how you can use the rand function to do what you want.  This code should work for what you want.
0
 
TEFKASGCommented:
TEFKASG changed the proposed answer to a comment
0
All Courses

From novice to tech pro — start learning today.