Tri Par Comptage

Cette méthode consiste a construire un vecteur d’indices ind, dans lequel on calcule la position que devrait avoir chaque élément pour que le vecteur soit trié:

PROCEDURE tri_comptage (     v : vec_t;
vn : integer;
var w : vec_t);
VAR i, k : integer;
ind : array [1..VMax] of integer;
BEGIN
{ init }
for i := 1 to vn do ind[i] := 1;
{ construit ind }
for i := 1 to vn-1 do
for k := i+1 to vn do
if v[k] < v[i]
then ind[i] := ind[i]+1
else ind[k] := ind[k]+1;
{ construit w }
for i := 1 to vn do w[ind[i]] := v[i];
END;

Le coût
La place occupée est importante (3 vecteurs).
Le nombre de comparaisons est constant (vn × (vn − 1)/2). C’est du même ordre que le tri par permutation ou a bulles non optimisé.  Il y a très peu d’affectations (vn) ; cela est très intéressant si les éléments de vn sont « lourds », par exemple des strings ou des records triés sur un champ.

Voire aussi un petit tuto copier de comment ça marche :

Pour i allant de 1 a (fin de tableau)
Res(i) = 0
Nb(i) = 0
'calcule des compteurs
Pour j allant de 1 a (fin de tableau)
Si tableau(j) < tableau(i) alors
Nb(i) = nb(i) + 1
Fin de si
Fin de pour
Fin de pour
Pour i allant de 1 a (fin de tableau)
j = nb(i)
Tant que res(j) <> 0 'cas des doubles
j = j + 1
Fin de tant que
Res(j) = tableau(i)
Fin de pour