Tri de tri en C. Pourquoi?

Question

C'est simple code en C (sorte de sélection):

#include <stdio.h> 
#include <stdlib.h> 
#define ItemCount 10 

int numbers[ItemCount] = {4,9,3,7,2,5,10,2,12,6};  


int MinNumberIndex(int start) 
{ 
     int i; 
      int minindex = start; 

      for(i=start+1;i<ItemCount;i++) 
        if(numbers[minindex]>numbers[i]) minindex = i; 

       return minindex;  
} 


void SelectionSort() 
{ 

      int i,temp,minindex; 

      for (i=0;i<10;i++) 
      { 
       minindex = MinNumberIndex(i); 

       temp = numbers[i]; 
       numbers[i] = numbers[minindex ]; 
       numbers[minindex ] = temp;                   
      } 


} 

int main() 
{ 

     int i; 

SelectionSort(); 
for(i = 0;i<10;i++) printf("%d\t",numbers[i]); 

system("pause"); 

} 

Et cela fonctionne bien ... mais si je change un peu comme celui-ci (en fonction SelectionSort):

for (i=0;i<10;i++) 
      { 

       temp = numbers[i]; 
       numbers[i] = numbers[MinNumberIndex(i)]; 
       numbers[MinNumberIndex(i)] = temp;                   
      } 

ça ne marche pas ... Pourquoi? Cela semble être la même chose.

Answer 1

La valeur renvoyée par MinNumberIndex dépend du contenu du tableau. Vous changez le contenu lorsque vous faites:

numbers[i] = numbers[MinNumberIndex(i)]; 

de sorte que le prochain appel:

numbers[MinNumberIndex(i)] = temp; 

va/peut stocker à la mauvaise cellule depuis MinNumberIndex (i) peut avoir changé. Cela casse l'algorithme parce que vous ne faites pas un bon échange.

Answer 2

Parce que MinNumberIndex(i) renvoie des valeurs différentes chaque fois que vous l'appelez, la deuxième version n'est donc pas un échange de valeurs.

Answer 3

Depuis MinNumberIndex(i) renvoie l'index de l'élément le plus petit dans la gamme [i,ItemCount-1] et votre version alternative du code modifie cette gamme dans le tableau entre les deux appels à MinNumberIndex(), vous n'êtes pas échanger des éléments.

Votre boucle alternative est eqivalent à:

for (i=0;i<10;i++) 
     { 

      temp = numbers[i]; 
      numbers[i] = numbers[MinNumberIndex(i)]; 
      numbers[i] = temp;                   
     } 

un peu plus en détail, lorsque cette ligne de code est exécuté dans la boucle for:

numbers[i] = numbers[MinNumberIndex(i)]; 

Il fait numbers[i] le minimum dans la plage de gamme que vous avez affaire à ce moment, donc la prochaine fois que MinNumberIndex(i) est appelée, il renverra i. Et

numbers[i] = temp; 

va juste restaurer le tableau dans le même état où il était en haut de la boucle.