 |
|
 |
|
 |
16 - QUICKSORT - TRI RAPIDE
|
|
|
|
PRÉSENTATION :
Implémentation de la méthode du tri rapide.
NOTES :
Le programme d'exemple montre la différence de vitesse entre le 'tri à bulles' et le 'tri rapide'. Dans le cas de tableau de faible taille ( quelques centaines d'éléments ),
le tri à bulles est bien suffisant, mais dans le cas de tableau très importants le 'tri rapide' doit être utilisé.
Le tri est ici appliqué à des tableaux d'entiers, mais il est facile de l'adapter à d'autres types.
CODE :
Procedure TriABulles(Var Tab:Array Of Integer);
Var i,j,t:Integer;
Begin
For i:=Low(Tab) To High(Tab)-1 Do For j:=i+1 To High(Tab) Do If Tab[i]>Tab[j] Then
Begin
t:=Tab[i];
Tab[i]:=Tab[j];
Tab[j]:=t;
End;
End;
Procedure TriRapide(Var Tab:Array Of Integer);
Var i,j,t:Integer;
Function Partition(m,n:Integer):Integer;
Var i,j,v:Integer;
Begin
v:=Tab[m];
i:=m-1;
j:=n+1;
While True Do
Begin
Repeat Dec(j) Until Tab[j]<=v;
Repeat Inc(i) Until Tab[i]>=v;
If (i<j)
Then Begin
t:=Tab[i];
Tab[i]:=Tab[j];
Tab[j]:=t;
End
Else Begin
Result:=j;
Exit;
End;
End;
End;
Procedure FaitTri(m,n:Integer);
Var p:Integer;
Begin
If m<n
Then Begin
p:=partition(m,n);
FaitTri(m,p);
FaitTri(p+1,n);
End;
End;
Begin
FaitTri(Low(Tab),High(Tab));
End;
|
| |
 |
|
 |
Les sources présentées sur cette page sont libres de droits,
et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation
constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright ©
2003 Bruno Guérangé. Aucune reproduction,
même partielle, ne peut être faite de ce site et de l'ensemble de son contenu :
textes, documents, images, etc sans l'autorisation expresse de l'auteur.
Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E
de dommages et intérêts.
Cette page est déposée à la
SACD.
|
