Méthode de tri rapide ( quick-sort )

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

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)