16 - QUICKSORT - TRI RAPIDE

Le petit coin du web de Nono40

http://nono40.developpez.com

SOURCES

PRÉSENTATION : Implémentation de la méthode du tri rapide.

ZIP : Téléchargez le zip

APERÇUS :

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 œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2003 Bruno Guérangé. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.