Trouver le 2e élément le plus grand dans un tableau avec un nombre minimal de comparaisons

Question

Pour un tableau de taille N, quel est le nombre de comparaisons requises?

Answer 1

L'algorithme optimal utilise n+log n-2 comparaisons. Pensez à des éléments comme des concurrents, et un tournoi est de les classer.

Tout d'abord, comparer les éléments, comme dans l'arbre

   |
  / \
 |   |
/ \ / \
x x x x

cela prend n-1 comparaisons et chaque élément est impliqué dans la comparaison au plus log n fois. Vous trouverez le plus grand élément en tant que gagnant.

Le deuxième élément doit avoir perdu un match pour le gagnant (il ne peut pas perdre un match à un autre élément), de sorte qu'il est le journal de n éléments, le gagnant a joué contre. Vous pouvez trouver lequel d'entre eux à l'aide de log n - 1 comparaisons.

L'optimalité est prouvé par adversaire argument. Voir http://math.stackexchange.com/questions/1601 ou http://compgeom.cs.uiuc.edu/~jeffe/enseignement/497/02-sélection.pdf ou http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf ou https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

Answer 2

Vous pouvez trouver la deuxième plus grande valeur avec au plus 2 · ( N -1) comparaisons et deux variables contenant la plus grande et la deuxième plus grande valeur:

 largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
    number := numbers[i];
    if number > largest then
        secondLargest := largest;
        largest := number;
    else
        if number > secondLargest then
            secondLargest := number;
        end;
    end;
end;
 

Answer 3

L'utilisation de la Bulle de tri ou de Sélection de l'algorithme de tri qui trie le tableau par ordre décroissant. Ne pas trier le tableau complètement. Seulement deux passes. Premier passage donne le plus grand élément et le second passage vous donnera le deuxième plus grand élément.

Pas de. des comparaisons de premier passage: n-1 Pas de. des comparaisons de premier passage: n-2 Non totale. de comparaison pour trouver le deuxième plus grand: 2n-3

Peut-être vous pouvez généraliser cet algorithme. Si vous avez besoin de la 3ème plus grande puis vous faire 3 passes.

Par la stratégie ci-dessus, vous n'avez pas besoin de toutes les variables temporaires comme la Bulle de tri et de Sélection, de tri sont en place des algorithmes de tri.

Answer 4

Voici du code qui pourrait ne pas être optimal mais qui au moins trouve réellement le 2e plus grand élément:

 if( val[ 0 ] > val[ 1 ] )
{
    largest = val[ 0 ]
    secondLargest = val[ 1 ];
}
else
{
    largest = val[ 1 ]
    secondLargest = val[ 0 ];
}

for( i = 2; i < N; ++i )
{
    if( val[ i ] > secondLargest )
    {
        if( val[ i ] > largest )
        {
            secondLargest = largest;
            largest = val[ i ];
        }
        else
        {
            secondLargest = val[ i ];
        }
    }
}
 

Il faut au moins N-1 comparaisons si les 2 éléments les plus grands se trouvent au début du tableau et au plus 2N-3 dans le pire des cas (l'un des 2 premiers éléments est le plus petit du tableau).

Answer 5

cas 1 -> 9 8 7 6 5 4 3 2 1
cas 2 -> 50 10 8 25 ........
cas 3 -> 50 50 10 8 25 .........
cas 4 -> 50 50 10 8 50 25 .......

 public void second element()  
{
      int a[10],i,max1,max2;  
      max1=a[0],max2=a[1];  
      for(i=1;i<a.length();i++)  
      {  
         if(a[i]>max1)  
          {
             max2=max1;  
             max1=a[i];  
          }  
         else if(a[i]>max2 &&a[i]!=max1)  
           max2=a[i];  
         else if(max1==max2)  
           max2=a[i];  
      }  
}