Ce programme présente une implémentation de la méthode du tri rapide. Cette méthode est beaucoup plus rapide que le tri a bulles couramment utilisé.
Par exemple, sur mon PC ( P750 WinME ) un tableau de 10000 entiers est trié en 710 ms avec le tri à bulles et en moins de 10ms avec le tri rapide. et 50ms pour 100000 entiers ( pour le tri à bulles je n'ai pas eu la patience d'attendre la fin... )
Source / Exemple :
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;
Conclusion :
PS. dans le programme exemple, seules les listes de moins de 1000 entiers sont affichées, mais vous pouvez demander le calcul sur des tableaux biens plus grand. Attention : le calcul 'tri à bulles' peut facilement durer des heures et des heures...
Je sais que j'avais vu en cours cette méthode il y a bien longtemps, mais je l'avais oubliée. J'ai trouvé une source ici :
http://cermics.enpc.fr/polys/info1-98/node103.html
Si vous voulez plus d'infos sur cette méthode utilisez le mot clef "Quicksort".
------------------
Cette source et quelques autres sur :
http://nono40.developpez.com
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.