Sélection Tri - Index de Min/Max

Question

Je regardais à travers l'algorithme de tri de sélection sur cprogramming.com et je pense avoir trouvé une erreur dans l'implémentation. Si vous travaillez à travers l'algorithme, il y a une variable appelée "index_of_min" qui, je crois, devrait être "index_of_max" (depuis que je l'ai testée, elle était la plus grande à la plus petite).

En pensant que c'était une faute de frappe ou une erreur mineure, j'ai vérifié d'autres sites Web comme wikipedia et certains sites moins connus comme geekpedia. Il semble qu'ils s'appellent l'indice de min. Lorsque je l'ai exécuté dans le débogueur, il m'a vraiment semblé que c'était l'index de la valeur max. Est-ce que je fais une erreur quelque part? Edit: Comme l'a souligné Svante, seule l'implémentation de la programmation est fausse. Wikipedia et Geekpidia vont bien.

Answer 1

Les sites wikipedia et geekpedia semblent être corrects, l'implémentation de cprogramming.com a en fait un bug; ceci:

if (array[index_of_min] < array[y]) 
    { index_of_min = y; } 

a l'ordre inverse, il devrait être:

if (array[y] < array[index_of_min]) 
    { index_of_min = y; } 

Une autre solution serait d'appeler la index_of_max variable mais j'attendre un algorithme de tri pour trier le plus petit au plus grand, et si cette attente est partagée par la majorité des programmeurs (comme je le suppose), le principe du moindre étonnement exige plutôt la solution ci-dessus.

Answer 2

Vous avez raison. Le code de ce site Web (illustré ci-dessous) est incorrect.

for(int x = 0; x < n; x++) 
    { 
     int index_of_min = x; 
     for(int y = x; y < n; y++) 
     { 
      if(array[index_of_min] < array[y]) /* Here's the problem */ 
      { 
       index_of_min = y; 
      } 
     } 
     int temp = array[x]; 
     array[x] = array[index_of_min]; 
     array[index_of_min] = temp; 
    } 

A la fin de la boucle interne, for(int y=x; y<n; y++), la variable, index_of_min, contient l'indice de la valeur maximale. En supposant que c'était conçu pour trier le tableau de plus grand au plus petit, ceci est un mal nommé variable.

Si vous voulez que le tableau trié plus petit au plus grand (comme on pouvait s'y attendre), vous devez inverser l'instruction if:

if (array[y] < array[index_of_min]) 
{ 
    index_of_min = y; 
} 

Profitez,

Robert C. Cartaino

Answer 3

Je viens juste de lire le code, mais on dirait que vous avez raison: soit index_of_min est mal nommé ou la comparaison est à l'envers.

Il n'est pas aussi étrange que cela puisse paraître à plusieurs endroits. Il est fort probable que chacun soit copié à partir d'une seule source commune.

Answer 4

De Cprogramming.com "Cela fonctionne en sélectionnant le plus petit (ou le plus grand, si vous voulez trier du plus grand au plus petit) élément du tableau et en le plaçant en tête du tableau" Donc ils l'ont trié de grand à petit, le code est faux , ni la dénomination des variables, index_of_min garde une trace du point de départ dans le tableau (0), puis avance dans ce tableau. ie index_of_min conserve la plus petite valeur d'index. Ne le confondez pas avec la valeur de cet index.