Tri par insertion

Bonjour,

Je cherche à présent à faire un tri par insertion: voici mon programme.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public static void sort(Comparable[]tab){ int m=0; for (int i=0; i<tab.length; i++){ /*Parcourir le tableau*/ for(int j=1; tab[j].compareTo(tab[i])<0; j++){ /*Trouver la place où il faut insérer*/ m=j; } tab[m]=tab[i]; /*Recopier l'élément à inséréer*/ for(int k=i; k>m; k--){ tab[k]=tab[k-1]; } }   }

---

Mais j'ai un problème dans mon programme. Pouvez vous m'aider svp?
Merci

Il y a quelques erreurs:
- m est mal initialisé et trop tôt : initialise le à i dans ta boucle
- j doit être initialisé à 0 et pas à 1 : problème si tab[i] doit s'insérer en première position ...
- Le test tab[j].compareTo(tab[i])<0 arrête ta boucle à tab[i] ou sur l'élément d'insertion (OK) MAIS m n'a pas encore été ajusté à la valeure de j
- tab[m] n'a pas été sauvegardé avant d'être écrasé par tab[i]
- tab[i] doit être inséré APRES avoir décalé le tableau

Solutions :
- Oublie la variable m et utilise directement j pour la position de l'insertion
- Avant d'insérérer tab[i] test si c'est pertinant de le faire (j<i ) ?
- Sauve tab[i], décale le tableau et ensuite insère la valeure sauvegardée de tab[i]

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public static void sort(Comparable[]tab){   for (int i=0; i<tab.length; i++){ /*Parcourir le tableau*/ int j; // <<< j remplace m for(j=0 /*<<< zéro et pas 1 */; tab[i].compareTo(tab[j])>0; j++){ /*Trouver la place où il faut insérer*/ }   if (j<i) { // <<< Faut-il insérer tab[i] ? ... // tab[m]=tab[i]; <<< Faire ceci seulement après avoir décalé le tableau Comparable tabI=tab[i]; // <<< Sauver Tab[i] avant de décaler le tableau for(int k=i; k>j; k--){ tab[k]=tab[k-1]; // Lorsque k=i tab[i] est écrasé par tab[i-1] } tab[j]=tabI; /*Recopier l'élément à inséréer*/ } } }

---