Méthode de tri rapide ( quick-sort )
Soyez le premier à donner votre avis sur cette source.
Vue 17 361 fois - Téléchargée 633 fois
Description
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... )
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
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
Codes Sources
A voir également
- Quicksort pascal
- Tri rapide pascal - Meilleures réponses
- Quicksort delphi - Meilleures réponses
- Python : Tri rapide (Quick sort) - CodeS SourceS - Guide
- Tri rapide c++ - Guide
- C / C++ / C++.NET : Tri rapide - CodeS SourceS - Guide
- Visual Basic / VB.NET : Tri rapide (quicksort) d'un tableau de chaînes de caractères - - Guide
- C# / .NET : La mÉthode du tri a bulles en c# - CodeS SourceS - Guide
Commentaires
(extrait d'un logiciel de spéléo)
TSynclinalDatabase: objet correpondant au gestionnaire de BD du logiciel
GetCavite(Index): Extrait de la base de données la cavité numéro Index
PutCavite(Index, Cavite): Ecrit dans la base de données l'enregistrement Cavité à la position Index
Dans la ligne:
if (bidon1=ridx) then Exit;
mid:=(lidx+ridx) div 2;
Buffer:=GetCavite(lidx);
PutCavite(lidx, GetCavite(mid));
PutCavite(mid, Buffer);
e:=lidx;
for k:=1+lidx to ridx do begin
C1:=GetCavite(k);
C2:=GetCavite(lidx);
// tri sur les clés
bidon1:=C1.IDCavite;
bidon2:=C2.IDCavite;
if (bidon1<bidon2) then begin
Inc(e);
Buffer:=GetCavite(e);
PutCavite(e, GetCavite(k));
PutCavite(k, buffer);
end;
end;
Buffer:=GetCavite(lidx);
PutCavite(lidx, GetCavite(e));
PutCavite(e, Buffer);
QSortByKey(lidx, e-1);
QSortByKey(e+1, ridx);
end;
begin
AfficherMessage('Tri de la base');
if NbCavites=0 then Exit;
QSortByKey(0, NbCavites-1);
end;
Merci
TJoueurInfo = record
Nickname: string;
Points : word;
end;
-------------------------
Procedure TJoueursList.TrieTab(VAR T : array of TJoueurInfo; Inf, Sup: WORD);
Procedure Swap(VAR S1, S2 : TJoueurInfo);
VAR Tmp: TJoueurInfo;
BEGIN
Tmp := S1 ;
S1 := S2 ;
S2 := Tmp ;
END;
VAR i,j:WORD;
BEGIN
IF Inf >= Sup THEN
ELSE BEGIN
i := Inf + 1 ;
j := Sup ;
While Not (i >= j) Do //i=j pour le cas où Sup=Inf+1
Begin
While Not (( T[i].Points > T[Inf].Points ) Or (i = j)) Do INC(i) ; //on cherche le 1er élément > T[Inf] à partir de la gauche
While Not (( T[j].Points < T[Inf].Points ) Or (j = i-1)) Do DEC(j) ; //on cherche le 1er élément < T[Inf] à partir de la droite
If i < j Then Swap(T[i], T[j]) ; //on les intervertit. Cette instruction pourrait être placée sans test juste après le WHILE
End;
If T[j].Points < T[Inf].Points Then Swap(T[Inf], T[j]) ; //on a donc ts les T<T[Inf] à gauche et les autres à droite
if j <> 0 then
TrieTab (T, Inf, j-1); //reste à trier la partie gauche
TrieTab (T, j+1, Sup) //et la partie droite
End;
END;
----------------------------------
Le paramètre Inf et Sup correspond à l'interval qui sera trié. Pour effectuer un trie complet on appelle donc la fonction avec ces paramètres:
TrieTab(UnTableau, 0, Count - 1);
L'algorithme utilisé est biensûr QuickSort mais présenté d'une autre manière.
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.