Code source complet : Implémentation simple du tri rapide

Algorithmique > Algorithmes de tri > Tri rapide [ Réagir ]

Informations

Implémentation simple du tri rapide (code source du 2006-10-29) :
C'est le premier élément du tableau ou sous-tableau à trier que l'on choisit comme pivot.

Code source complet (Pascal)

{==============================================================================}
unit UQuickSort;
{
               Algorithme du "tri rapide" ou "quick sort"

  Date          : 29 octobre 2006
  Documentation : http://www.uzit.fr/algorithmique/tri-rapide.html

--------------------------------------------------------------------------------

Utilisation de la procédure QuickSort :
   * Paramètres : (A : Tableau à trier)
                  (N : Nombre d'éléments du tableau A)
   * Sortie     : (Aucune)
                  (Le tableau A passé en paramètre est trié)

Adaptations de la procédure QuickSort :
   * Pour changer le type de données à trier, modifier les déclarations
     de type des types TMyType et TMyTypeArray
   * Pour modifier le critère de tri, adapter la fonction Compare() ;
     celle-ci renvoie True si un élément de valeur (aV) doit être placé
     avant un élément de valeur (aW) dans le tableau trié
                                                                               }
{==============================================================================}

interface

type

  TMyType = Int64;
  TMyTypeArray = Array of TMyType;

  procedure QuickSort(var A: TMyTypeArray; N: Integer);
                                            
  function Compare(aV,aW: TMyType): Boolean;
  procedure QSort_Conquer(var A: TMyTypeArray; Left,Right: Integer);
  function QSort_Divide(var A: TMyTypeArray; Left,Right: Integer): Integer;

implementation

procedure QuickSort(var A: TMyTypeArray; N: Integer);
begin

  QSort_Conquer(A,0,N-1);

end;

function Compare(aV,aW: TMyType): Boolean;
begin

  Result:=(aV<aW);

end;

procedure QSort_Conquer(var A: TMyTypeArray; Left,Right: Integer);
var Pivot: Integer;
begin

  if (Left<Right) then
    begin
      Pivot:=QSort_Divide(A,Left,Right);
      QSort_Conquer(A,Left,Pivot-1);
      QSort_Conquer(A,Pivot+1,Right);
    end;

end;

function QSort_Divide(var A: TMyTypeArray; Left,Right: Integer): Integer;

  procedure Switch(V,W: Integer);
  var Tmp: TMyType;
  begin
    Tmp:=A[V];
    A[V]:=A[W];
    A[W]:=Tmp;
  end;

var I: Integer;
    PivotValue: TMyType;
begin

  Result:=Left;
  PivotValue:=A[Left];

  For I:= Left+1 to Right do
    if Compare(A[I],PivotValue) then
      begin
        Result:=Result+1;
        Switch(Result,I);
      end;
  Switch(Result,Left);

end;

end.