Procédure de tri à bulles

Marsh Posté le 02-03-2009 à 23:57:55

Bonsoir,

Ayant vu en cours une procédure de tri à bulles que je n'ai pas bien comprise, je vous la poste, en espérant que vous pourrez m'éclairer quelque peu:

Code :

PROCEDURE Tri_Bulles(T: IN OUT Tableau) IS
Aux: Integer;
Tri_Fini: Boolean;
Nbre_Passes: Natural :=0;
BEGIN
WHILE NOT Tri_Fini LOOP
Nbre_Passes := Nbre_Passes + 1;
Tri_Fini := True;
FOR I IN T'First..T'Last-Nbre_Passes LOOP
IF T(I) > T(I+1) THEN
Tri_Fini := False;
Aux := T(I);
T(I) := T(I+1);
T(I+1) := Aux;
END IF;
END LOOP;
END LOOP;
END Tri_Bulles;

Dans cette situation, je ne parviens pas à faire "tourner" la procédure sur un exemple simple. Notamment, je ne comprends pas pourquoi Nbre_Passes := Nbre_Passes + 1 et Tri_Fini := True sont placés là où ils sont.. Pourriez-vous peut-être me détailler un peu comment les choses se passent sur un exemple? Par exemple sur le tableau (vecteur) 3741?

J'applique la procédure de tri à ce vecteur à 4 "composantes":

- Je rentre dans la boucle While;
- Dès lors, on a Nbre_passes qui se retrouve égal à 1! (0(valeur initiale) + 1) Pourquoi ne fait-on pas le cas Nbre_passes:= 0 dans la boucle? Vu qu'on commence à la valeur 1, on n'a jamais un parcours complet du tableau (de T'First à T'Last)! N'est-ce pas ennuyeux de ne pas accéder à la dernière case? Il me semble que si..
- Suite...?

Merci d'avance!

Reply

Marsh Posté le 02-03-2009 à 23:57:55

Reply

Marsh Posté le 03-03-2009 à 00:19:07

http://en.wikipedia.org/wiki/Bubble_sort

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box, and replicate and expand beyond their wildest dreams by throwing away the limits imposed by overbearing genetic r

Reply

Marsh Posté le 03-03-2009 à 09:13:05

Un exemple simple => 1 - 10 -2 - 9 à trier

Essayons de Dérouler le programme

* 1ere passe

tri_fini <- True
t(1) > t(2) => non ! 1 - 10 reste tel quel

t(2) > t(3) => oui ! inversion 10 - 2 devient 2 - 10
tri_fini <- False

t(3) > t(4) => oui ! inversion 10 - 9 devient 9 - 10
tri_fini <- False

résultat 1ere passe donne 1 - 2 - 9 - 10

* 2eme passe

tri_fini <- True

t(1) > t(2) => non ! 1 - 2 reste tel quel
t(2) > t(3) => non ! 2 - 9 reste tel quel
t(3) > t(4) => non ! 9 - 10 reste tel quel

Fin de programme car pas de changement détecté donc tri OK

ça va mieux ?

---------------
il n'y a pas que le VTT dans la vie, il y a le Snowboard aussi ...

Reply

Procédure de tri à bulles

Sujets relatifs:

Leave a Replay