Code source complet : Implémentation simple du tri fusion

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

Informations

Implémentation simple du tri fusion (code source du 2006-11-01) :
Implémentation récursive du tri fusion avec création de tableaux temporaires.

Code source complet (Pascal)

{==============================================================================}
unit UMergeSort;
{
                     Algorithme du "tri fusion"

  Date          : 1 novembre 2006
  Documentation : http://www.uzit.fr/algorithmique/tri-fusion.html

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

Utilisation de la procédure MergeSort :
   * 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 MergeSort :
   * 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 MergeSort(var A: TMyTypeArray; N: Integer);

  function Compare(aV,aW: TMyType): Boolean;
  procedure Merge_Conquer(var A: TMyTypeArray; Left,Right: Integer);

implementation

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

  Merge_Conquer(A,0,N-1);

end;

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

  Result:=(aV<aW);

end;

procedure Merge_Conquer(var A: TMyTypeArray; Left,Right: Integer);
var DivideIndex,LeftIdx,RightIdx,I: Integer;
    P: PInteger;
    Tmp: Array of TMyType;
begin

  if (Left<Right) then
    begin

      DivideIndex:=(Right-Left) div 2;
      Merge_Conquer(A,Left,Left+DivideIndex);
      Merge_Conquer(A,Left+DivideIndex+1,Right);

      SetLength(Tmp,Right-Left+1);
      Move(A[Left],Tmp[0],(Right-Left+1)*SizeOf(TMyType));
      LeftIdx:=0;
      RightIdx:=DivideIndex+1;
      For I:= Left to Right do
        begin
          if (LeftIdx>DivideIndex) then P:=@RightIdx
          else
            if (RightIdx>Right-Left) then P:=@LeftIdx
            else
              if Compare(Tmp[LeftIdx],Tmp[RightIdx]) then P:=@LeftIdx
              else P:=@RightIdx;
          A[I]:=Tmp[P^];
          Inc(P^);
        end;
      Finalize(Tmp);

    end;

end;

end.