I.T.A.G (DTS1)
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.

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
 
AccueilPortailRechercherDernières imagesS'enregistrerConnexion
Le Deal du moment :
Xiaomi Mi Smart Camera 2K Standard Edition (design ...
Voir le deal
11.39 €

 

 Tri de tableau + flag = tri à bulles

Aller en bas 
AuteurMessage
mohcin




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

Tri de tableau + flag = tri à bulles Empty
MessageSujet: Tri de tableau + flag = tri à bulles   Tri de tableau + flag = tri à bulles Icon_minitimeMer 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
 
Tri de tableau + flag = tri à bulles
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Un exemple de flag : la recherche dans un tableau
» Tableau word

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:  
Ne ratez plus aucun deal !
Abonnez-vous pour recevoir par notification une sélection des meilleurs deals chaque jour.
IgnorerAutoriser