Le tri par insertion

Algorithmique > Algorithmes de tri > Tri par insertion [ Proposer une amélioration ]

Principe et optimisation

Le tri par insertion très largement utilisé pour trier des petits tableaux. En effet, c'est le tri le plus efficace pour des tableaux de petite taille. Certains algorithmes plus évolués, tels le tri rapide, utilisent le tri par insertion pour trier des sous-ensembles de tableaux beaucoup plus grands.

Il existe un tri plus rapide, le tri de Shell, basé sur le principe du tri par insertion.

Complexité en temps

Le tri par insertion a une complexité en temps de la forme Ω(n²).
Bien qu'il fasse partie des tris les plus lents sur des grands tableaux, sa complexité, qui est plus exactement en Ω((n²-n)/4) ne l'empêche pas d'être extrêmement rapide pour trier les petits tableaux.

Conditions et évolutions

Vous pouvez adapter l'algorithme de tri par insertion à vos besoins en suivant les consignes suivantes :

• Pour trier autre chose que des entiers, il suffit de modifier la déclaration de TMyType.
• Pour changer la fonction de compaison, il faut adapter la fonction Compare().
  Celle-ci renvoie "TRUE" si un élément de valeur aV doit être placé avant l'élément de valeur aW dans le tableau trié.

Il est aussi assez facile d'adapter l'algorithme de tri par insertion pour effectuer un véritable tri à l'insertion (en temps réel pas exemple). Cette propriété offerte par le tri par insertion est aussi valable pour le tri par tas.

Code (Pascal)

type TMyType = Int64;

procedure TriInsertion(var A: Array of TMyType; N: Integer);

  function Compare(aV,aW: TMyType): Boolean;
  begin
    Result:=(aV<aW);
  end;

var I,J,P: Integer;
    Tmp: TMyType;
begin

  For I:= 1 to N-1 do
    begin

      P:=0; While (Compare(A[P],A[I])) do P:=P+1;

      Tmp:=A[I];
      For J:= I-1 downto P do A[J+1]:=A[J];
      A[P]:=Tmp;

     end;

end;