Le tri comptage ou tri par casiers

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

Complexité en temps

Le tri comptage a une complexité en temps linéaire donc de la forme Ω(n).

Conditions

Pour utiliser le tri comptage, il est nécessaire que les données à trier soient des entiers naturels qui appartiennent à un intervalle relativement restreint. En effet, ce type de tri nécessite l'utilisation d'un tableau ayant pour taille le nombre d'entiers de cette intervalle.

Code (Pascal)

procedure CountingSort(var A: Array of Integer; MinimumValue,MaximumValue: Integer);
var I,Index: Integer;
    C: Array of Integer;
begin

  SetLength(C,MaximumValue-MinimumValue+1);
  For I:= 0 to Length(C)-1 do C[I]:=0;
  For I:= 0 to Length(A) do
    Inc(C[A[I]-MinimumValue]);
  Index:=0;
  For I:= 0 to Length(C)-1 do
    For J:= 1 to C[I] do
      begin
        A[Index]:=I+MinimumValue;
        Inc(Index);
      end;
  Finalize(C);

end;

Le code ci-dessus trie le tableau Α passé en paramètre ; tableau d'entiers, compris entre MinimumValue et MaximumValue. Après l'exécution de la procédure, le tableau Α est trié dans l'ordre croissant.