Méthode de tri rapide ( quick-sort )

Soyez le premier à donner votre avis sur cette source.

Vue 17 131 fois - Téléchargée 611 fois

Télécharger le projet
Commenter

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... )

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
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
balgrim
Messages postés
52
Date d'inscription
vendredi 26 avril 2002
Statut
Membre
Dernière intervention
28 octobre 2003
 -
ok, mais imaginont que ton array soit un array de type record, et que tu cherche à trier qu'une des valeur... g beau me creuser la tete je vois pas comment faire :s
Signaler
cs_DeeJay
Messages postés
23
Date d'inscription
mercredi 17 avril 2002
Statut
Membre
Dernière intervention
23 décembre 2003
 -
En voici la solution balgrim, ici on trie par le nombre de points un tableau de TJoueurInfo.
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.
Signaler
Andy_24DB
Messages postés
4
Date d'inscription
samedi 8 mai 2004
Statut
Membre
Dernière intervention
27 décembre 2005
 -
Mon prof de programmation théorique nous à même dit que c'était une variante du quicksort (mais basé sur le même principe)qui était utilisé par le moteur de recherche Google.

Merci
Signaler
speletux
Messages postés
31
Date d'inscription
jeudi 31 mars 2005
Statut
Membre
Dernière intervention
6 février 2014
 -
On peut même utiliser cet algo pour un fichier:
(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;
S'inscrire maintenant

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.

Du même auteur (cs_Nono40)