Discussion :

[bsangoku]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[rebel64]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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*/
		}
	}
}