Correction du TD n°8
Implanter en programmation algorithmique la méthode de tri par insertion appliquée aux tableaux d'entiers.
001 { Recherche de la position d'une valeur }
002 { a l'interieur d'un tableau trie d'entiers }
003
004 fonction indiceInsertion(t,v,imax) : entier
005 Donnees t : tableau [N] de entier { tableau ou chercher }
006 v : entier { valeur de recherche }
007 imax : entier { indice ultime de recherche }
008 Locales i : entier { indice de boucle }
009 i := 0
010 tant que (t[i] < v) et (i <= imax) faire
011 i := i+1
012 Resultat : i
013 fin fonction
001 { Decalage d'une cellule vers la droite }
002 { d'une partie d'un tableau d'entiers }
003
004 action decalage(t,ideb,ifin)
005 Donnees t : tableau [N] de entier { tableau d'entiers a decaler }
006 ideb : entier { indice de debut de decalage }
007 ifin : entier { indice de fin de decalage }
008 Locales i : entier { indice de boucle }
009 pour i de ifin à ideb pas -1 faire
010 t[i+1] = t[i];
011 fait
012 fin action
001 { Tri d'un tableau d'entiers par la methode }
002 { de tri par insertion }
003
004 action triInsertion(t)
005 Donnees / Resultat t : tableau [N] de entier { tableau d'entiers a trier }
006 Locales i : entier { indice de boucle }
007 aux : entier { variable auxiliaire }
008 indice : entier { indice d'insertion }
009 pour i de 1 à N-1 faire
010 indice := indiceInsertion(t,t[i],i-1)
011 si indice <> i alors
012 aux := t[i]
013 decalage(t,indice,i-1);
014 t[indice] := aux;
015 fsi
016 fait
017 fin action
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr
