Correction du TD n°7

Exercice 1

Implanter en programmation algorithmique la méthode de tri par sélection appliquée aux tableaux d'entiers.

001 { Tri d'un tableau d'entiers par la methode }
002 { de tri par selection }
003
004 action triSelection(t)
005 Donnees / Resultat t : tableau [N] de entier { tableau d'entiers a trier }
006 Locales i : entier { indice de boucle }
007 val : entier { variable auxiliaire }
008 indmin : entier { indice d'un minimum }
009 pour i de 0 à N-2 faire
010 indmin := indiceMinimum(t,i,N-1);
011 si i <> indmin alors
012 val := t[i]
013 t[i] := t[indmin]
014 t[indmin] := val
015 fsi
016 fait
017 fin action

TriSelection.lda

001 { Fonction de recherche de l'indice }
002 { de la valeur minimum d'un tableau }
003 { pour les seules valeurs de l'indice ideb }
004 { a l'indice ifin inclus }
005
006 fonction indiceMinimum(t,ideb,ifin) : entier
007 Donnees t : tableau [N] de entier { tableau de recherche }
008 ideb : entier { indice de debut de recherche }
009 ifin : entier { indice de fin de recherche }
010 Locales i : entier { indice de boucle }
011 imin : entier { indice du minimum recherche }
012 imin := ideb
013 pour i de ideb+1 à ifin faire
014 si t[i] < t[imin] alors
015 imin := i
016 fsi
017 fait
018 Resultat : imin
019 fin fonction

IndiceMinimum.lda

Exercice 2

Implanter en programmation algorithmique la méthode de tri à bulle appliquée aux tableaux d'entiers.

001 { Tri d'un tableau d'entiers par la methode }
002 { de tri a bulle }
003
004 action triABulle(t)
005 Donnees / Resultat t : tableau [N] de entier { tableau d'entiers a trier }
006 Locales i : entier { indice de boucle }
007 val : entier { variable auxiliaire }
008 limite : entier { limite de parcours }
009 permutation : booleen { permutation? sur la passe }
010 { en cours }
011 limite := N-2
012 permutation := vrai
013 tant que permutation faire
014 permutation := faux
015 pour i de 0 à limite faire
016 si t[i] > t[i+1] alors
017 val := t[i]
018 t[i] := t[i+1]
019 t[i+1] := val
020 permutation := vrai
021 fsi
022 fait
023 limite := limite-1
024 fin tantque
025 fin action

TriABulle.lda

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr