Correction du TD n°5 et du TD n°6
Une fonction pour rechercher l'indice de la valeur minimum d'un sous-tableau d'un tableau.
001 fonction indiceDuMinimum(t,ideb,ifin):entier
002 Données t : Tableau [N] de entier { Tableau ou rechercher }
003 ideb : entier { Indice a partir duquel commencer a chercher }
004 ifin : entier { Indice jusqu'auquel effectuer la recherche }
005 Locales ind : entier
006 i : entier
007 ind := ideb
008 pour i de ideb+1 à ifin faire
009 si t[i] < t[ind] alors
010 ind := i
011 fsi
012 fait
013 Resultat : ind
014 fin fonction
Une action pour effectuer le tri par sélection.
001 action triSelection(t)
002 Données-Résultats t : Tableau [N] de entier { Tableau a trier }
003 Locales deb : entier { Indice de boucle pour }
004 imin : entier { Indice de valeur minimale }
005 v : entier { Variable auxiliaire de permutation }
006 pour deb de 0 à N-2 faire
007 imin := indiceDuMinimum(t,deb,N-1)
008 v := t[deb]
009 t[deb] := t[imin]
010 t[imin] := v
011 fait
012 fin action
Une action pour effectuer le tri à bulle.
001 action triBulle(t)
002 Données-Résultats t : Tableau [N] de entier { Tableau a trier }
003 Locales stop : booleen { Condition d'arret du tri }
004 ind : entier { Compteur du nombre de valeurs triees }
005 i : entier { Indice de boucle pour }
006 v : entier { Variable auxiliaire pour permutation }
007 stop := faux
008 ind := 0
009 tant que non(stop) faire
010 stop := vrai
011 pour i de 0 à N-2-ind faire
012 si t[i] > t[i+1] alors
013 stop := faux
014 v := t[i]
015 t[i] := t[i+1]
016 t[i+1] := v
017 fsi
018 ind := ind + 1
019 fait
020 fin action
Une fonction pour rechercher la position d'insertion d'une valeur d'un tableau à la place dans le tableau qui le maintient trié.
001 fonction indiceInsertion(ind,t) : entier
002 Données ind : entier { Indice de la valeur du tableau t pour laquelle }
003 { on recherche la position d'insertion }
004 { entre t[0] et t[ind-1] }
005 t : Tableau [N] de entier { Tableau ou la recherche est effectuée }
006 Locales i : entier { Indice de recherche }
007 i := 0
008 tantque t[i] < t[ind] faire
009 i := i+1
010 fait
011 Résultat : i
012 fin fonction
Une action pour réaliser l'insertion d'une valeur d'un tableau dans ce même tableau.
001 action insertion(pos,t,src)
002 Données pos : entier { Indice ou l'insertion est realisee }
003 Données-Résultats t : Tableau [N] de entier { Tableau ou l'insertion est realisee }
004 Données src : entier { Indice de la valeur de t a inserer }
005 Locales v : entier { Variable auxiliaire de permutation }
006 i : entier { Indice de boucle pour }
007 v := t[src]
008 pour i de src à pos+1 pas -1 faire
009 t[i] := t[i-1]
010 fait
011 t[pos] := v
012 fin action
Une action pour effectuer le tri par insertion.
001 action triInsertion(t)
002 Données-Résultats t : Tableau [N] de entier { Tableau a trier }
003 Locales i : entier { Indice de boucle pour }
004 indice : entier { Indice d'insertion d'une valeur }
005 pour i de 1 à N-1 faire
006 indice := indiceInsertion(i,t)
007 si indice <> i alors
008 insertion(indice,t,i)
009 fsi
010 fait
011 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
