I.T.A.G (DTS1)

Ce forum incha allah aura pour but d aider les etudiant de la DTS1 a en plus savoir cotee cours et tt que sa soit reseau ou devlopment
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Tri de tableau + flag = tri à bulles

Aller en bas 
AuteurMessage
mohcin



Messages : 26
Date d'inscription : 13/02/2008

MessageSujet: Tri de tableau + flag = tri à bulles   Mer 13 Fév - 9:48

Et maintenant, nous en arrivons à la formule magique : tri de tableau + flag = tri à bulles.
L’idée de départ du tri à bulles consiste à se dire qu’un tableau trié en ordre croissant, c’est un tableau dans lequel tout élément est plus petit que celui qui le suit. Cette constatation percutante semble digne de M. de Lapalisse, un ancien voisin à moi. Mais elle est plus profonde – et plus utile - qu’elle n’en a l’air.
En effet, prenons chaque élément d’un tableau, et comparons-le avec l’élément qui le suit. Si l’ordre n’est pas bon, on permute ces deux éléments. Et on recommence jusqu’à ce que l’on n’ait plus aucune permutation à effectuer. Les éléments les plus grands « remontent » ainsi peu à peu vers les dernières places, ce qui explique la charmante dénomination de « tri à bulle ». Comme quoi l’algorithmique n’exclut pas un minimum syndical de sens poétique.
En quoi le tri à bulles implique-t-il l’utilisation d’un flag ? Eh bien, par ce qu’on ne sait jamais par avance combien de remontées de bulles on doit effectuer. En fait, tout ce qu’on peut dire, c’est qu’on devra effectuer le tri jusqu’à ce qu’il n’y ait plus d’éléments qui soient mal classés. Ceci est typiquement un cas de question « asymétrique » : il suffit que deux éléments soient mal classés pour qu’un tableau ne soit pas trié. En revanche, il faut que tous les éléments soient bien rangés pour que le tableau soit trié.
Nous baptiserons le flag Yapermute, car cette variable booléenne va nous indiquer si nous venons ou non de procéder à une permutation au cours du dernier balayage du tableau (dans le cas contraire, c’est signe que le tableau est trié, et donc qu’on peut arrêter la machine à bulles). La boucle principale sera alors :
Variable Yapermute en Booléen
Début

TantQue Yapermute

FinTantQue
Fin
Que va-t-on faire à l’intérieur de la boucle ? Prendre les éléments du tableau, du premier jusqu’à l’avant-dernier, et procéder à un échange si nécessaire. C’est parti :
Variable Yapermute en Booléen
Début

TantQue Yapermute
Pour i ← 0 à 10
Si t(i) > t(i+1) Alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Finsi
i suivant
Fin
Mais il ne faut pas oublier un détail capital : la gestion de notre flag. L’idée, c’est que cette variable va nous signaler le fait qu’il y a eu au moins une permutation effectuée. Il faut donc :
lui attribuer la valeur Vrai dès qu’une seule permutation a été faite (il suffit qu’il y en ait eu une seule pour qu’on doive tout recommencer encore une fois).
la remettre à Faux à chaque tour de la boucle principale (quand on recommence un nouveau tour général de bulles, il n’y a pas encore eu d’éléments échangés),
dernier point, il ne faut pas oublier de lancer la boucle principale, et pour cela de donner la valeur Vrai au flag au tout départ de l’algorithme.
La solution complète donne donc :
Variable Yapermute en Booléen
Début

Yapermut ← Vrai
TantQue Yapermut
Yapermut ← Faux
Pour i ← 0 à 10
Si t(i) > t(i+1) alors
temp ← t(i)
t(i) ← t(i+1)
t(i+1) ← temp
Yapermut ← Vrai
Finsi
i suivant
FinTantQue
Fin
Au risque de me répéter, la compréhension et la maîtrise du principe du flag font partie de l’arsenal du programmeur bien armé
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
 
Tri de tableau + flag = tri à bulles
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» intérprétation des % d'un tableau croisé
» urgent svp ,transformer en tableau de rang sous excel
» Deux bulles géantes au coeur de notre galaxie intriguent les astrophysiciens
» Tableau de recensement de nos idéolangues
» tableau numérique

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
I.T.A.G (DTS1) :: Cours de Réseaux et Development :: Devlopment :: cours-
Sauter vers: